Mirror a binary tree

Mirroring a binary tree, a common question nowadays to understand whether the candidate knows about tree traversal.

Correct code for creating mirrored tree, in-place

- do a post order traversal to read the full tree into the recursion stack

- do the primitive swap operation
https://www.geeksforgeeks.org/write-an-efficient-c-function-to-convert-a-tree-into-its-mirror-tree/

(1)  Call Mirror for left-subtree    i.e., Mirror(left-subtree)
(2)  Call Mirror for right-subtree  i.e., Mirror(right-subtree)
(3)  Swap left and right subtrees.
          temp = left-subtree
          left-subtree = right-subtree
          right-subtree = temp

    Node mirror(Node node)

    {

        if (node == null)

            return node;

  

        /* do the subtrees */

        Node left = mirror(node.left);

        Node right = mirror(node.right);

  

        /* swap the left and right pointers */

        node.left = right;

        node.right = left;

  

        return node;

    }




http://analgorithmaday.blogspot.com/2013/05/mirror-binary-tree.html

Tree* mirror(Tree* node)

{

    if(node == NULL)

        return NULL;

    mirror(node->left);

    mirror(node->right);

    Tree *tmp = node->left;

    node->left = node->right;

    node->right = tmp;

    return node;

}

Corrected code for reproduction of mirrored tree, as a copy

http://www.crazyforcode.com/mirror-image-binary-tree/

Tree* mirror(Tree* node)

{

    if(node == NULL)

        return NULL;

    Tree *newNode = createNode(node->data);

    newNode->left = mirror(node->right);

    newNode->right = mirror(node->left);

    return newNode;

}

struct node

02

{

03	int value;

04	struct node* left;

05	struct node* right;

06

};

07

08

09	struct node *mirrorTree(struct node *root)

10

{

11	struct node *temp;

12

13	if(root==NULL)

14	return(NULL);

15

16	temp = (struct node *) malloc(sizeof(struct node));

17	temp->value = root->value;

18

19	temp->left  = mirrorTree(root->right);

20	temp->right = mirrorTree(root->left);

21

22	return(temp);

23

}

Correct code for creating mirrored tree, in-place

- do a post order traversal to read the full tree into the recursion stack

Tree* mirror(Tree* node)

{

    if(node == NULL)

        return NULL;

    mirror(node->left);

    mirror(node->right);

    Tree *tmp = node->left;

    node->left = node->right;

    node->right = tmp;

    return node;

}

Iteratively mirror a tree

http://haixiaoyang.wordpress.com/2012/07/14/iteratively-mirror-a-tree/

void IterativeMirror(NODE* pRoot)

{

    if (NULL == pRoot)

        return;

    stack<NODE*> stk;

    stk.push(pRoot);

    while (!stk.empty())

    {

        NODE* pTop = stk.top();

        stk.pop();

        swap(pTop->pLft, pTop->pRgt);

        if (pTop->pLft != NULL)

            stk.push(pTop->pLft);

        if (pTop->pRgt != NULL)

            stk.push(pTop->pRgt);

    }

}

https://github.com/yadongwen/Company1-InterviewQuestions-Answers-Java/blob/master/mirror%20of%20binary%20tree.java
The order(swap or put to queue) doesn't matter.
    public static void mirrorIterative(TreeNode t) {
        if(t == null) return;
        LinkedList<TreeNode> q = new LinkedList<TreeNode>();
        q.add(t);
        while(!q.isEmpty()) {
            TreeNode tr = q.poll();
            if(tr.left != null) q.add(tr.left);
            if(tr.right != null) q.add(tr.right);
            TreeNode temp = tr.left;
            tr.left = tr.right;
            tr.right = temp;
        }
    }

void tree_mirror(struct node* node)

02

{

03	struct node *temp;

04

05	if (node==NULL)

06

{

07

return;

08

}

09

else

10

{

11	tree_mirror(node->left);

12	tree_mirror(node->right);

13

14	// Swap the pointers in this node

15	temp = node->left;

16	node->left = node->right;

17	node->right = temp;

18

}

19

}

http://algorithmproblems.blogspot.com/2012/12/are-two-binary-trees-mirror-image-of.html
Are two Binary Trees mirror image of each other?

boolean areMirrorTrees(BinaryTree a, BinaryTree b) {
    if (a == null && b == null) {
        return true;
    }
    if (a == null || b == null) {
        return false;
    }
    return a.data == b.data && areMirrorTrees(a.left, b.right)
            && areMirrorTrees(a.right, b.left);
}

http://www.acmerblog.com/offer11-2964.html

10	typedef struct Node {

11	struct Node * l;

12	struct Node * r;

13

int data;

14	}* pNode, Node;

15	char temp[2];

16	Node tree[1001];

17	//先右后左输出二叉树

18	void print(pNode root) {

19	if (root == 0)

20

return;

21	printf(" %d", root->data);

22	print(root->r);

23	print(root->l);

24

}

25	int main() {

26	while (~scanf("%d", &n)) {

27	for ( i = 1; i <= n; i++) {

28	scanf("%d", &tree[i].data);

29	tree[i].l = tree[i].r = 0;

30

}

31	for ( i = 1; i <= n; i++) {

32	scanf("%s %d", temp, &a);

33	if (temp[0] == 'd') {

34	tree[i].l = &tree[a];

35	scanf("%d", &a);

36	tree[i].r = &tree[a];

37	}else if(temp[0] == 'l')

38	tree[i].l = &tree[a];

39	else if(temp[0] == 'r')

40	tree[i].r = &tree[a];

41

}

42

if (n) {

43	printf("%d", tree[1].data);//由于空格判断，根节点单独输出

44	print(tree[1].r);

45	print(tree[1].l);

46

puts("");

47

} else

48	puts("NULL");

49

}

50

return 0;

51

}

Read full article from An Algorithm a Day: Mirror a binary tree