# Mirror of Binary Tree

[Ref]  
http://www.careercup.com/question?id=416409
http://www.careercup.com/question?id=7473670

Question-1 Write a function to check whether the Binary Tree is mirror structure.

True
True
(A (B (C,D), E( F,G)))
or
(A (B (C)), D(E)))

False
(A (B))
or
(A (B,C(D,E)))


ANS:
---> Let's do this slowly::
First, think about what if we would like to generate a mirror tree, how will you do it?
If do it recersively,
node RevBT(node n){
    if (n==NULL) return NULL;
      node temp = RevBT(n.left);
           n.left = RevBT(n.right);
          n.right = temp;
           return n;
}
Actually, if the BT is originally a bineary search tree, then you are actually doing that reverse the linked list, whic is a sorted array.
This is equivalent to -pre-order traversal, but this time we traverse root, then right-brance, then left-branch.

Now, we move to test whether the given tree is a mirror tree, this can be done to start from an input with two root, but has just "mirror" implementation for each:

root1 = root2 = giveBTroot;
bool mirrorBT(node root1, node root2){
    if (root1==NULL && root2 == NULL) return True;
           if (root1 ! = root2) return False;
           \\ now the left case is that roo1==roo2 but they do not = NULL
          return mirrorBT(roo1->left, roo2->right) && mirrorBT(root1->right, root2->left);
}

Question-2 "Mirror of Binary tree without recursion."
http://www.careercup.com/question?id=6721875
Anything we can do with recursion can be done without recursion using STACK
1. Push the node in the stack
2. Pop node from the stack and swap its left and right child
3. Push the right child followed by the left.
4. continue steps 1 to 3 till the stack is empty

1

     2         3
 4      5   6    7
stack: 1
pop 1: swap 2 and 3. Push 2 and 3 into the stack
stack: 2 3
pop 2: swap 4 and 5. Push 4 and 5 into the stack
stack: 4 5 3
pop 4: no children return
stack: 5 3
pop 5: no children return
stack: 3
pop 3: swap 6 and 7. Push 6 and 7 into the stack
stack: 6 7
pop 6: no children return
stack: 7
pop 7: no children return
o/p-->

 1

        3       2
      7  6    5  4

♥ ¸¸.•*¨*•♫♪♪♫•*¨*•.¸¸♥

Some other references: http://geeksforgeeks.org/?p=662