## Amazon Interview Question

Developer Program Engineersto get the mirror image of the binary tree we have to just traverse the tree in post

oreder and in a bottom up fashion we have to swap the right son to left

code :

void MirrorImage(struct node *R)

{

struct node *temp=NULL;

if(R==NULL||(R->left==NULL &&R->right==NULL))

return;

MirrorImage(R->left);

MirrorImage(R->right);

temp=R->left;

R->left=R->right;

R->right=temp;

}

Why is there a need to do it post order? We can swap the children and then call the function recursively on both the children, am I right? In the above written code, the function is called on children before they are swapped

Here is a crisp C++ function that mirrors a binary tree.

```
struct Node{
int data;
Node *left;
Node *right;
} *root;
Node* mirror(Node *node)
{
if(node==NULL)
return NULL;
else{
Node *leftSubtree = node->left;
Node *rightSubtree = node->right;
node->left = mirror(rightSubtree);
node->right = mirror(leftSubtree);
return node;
}
}
```

The invocation statement will be something like :

`root = mirror(root);`

```
//here is a solution without recursion using queues
q.enqueue(head);
mirror()
{
while(q.isNotEmpty())
{
node elem = q.dequeue();
if(elem.left==null && elem.right==null)
continue;
else
{
swap(elem.left, elem.right);
if(elem.left!=null) q.enqueue(elem.left);
if(elem.right!=null) q.enqueue(elem.right);
}
}
}
swap(node elem1, node elem2)
{
node temp = elem1;
elem1 = elem2;
elem2 = temp;
}
```

- Vir Pratap Uttam May 04, 2015