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