Problem: Please implement a function which returns mirror of a binary tree.
Binary tree nodes are defined as:
struct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};
Analysis: Mirror of binary trees may be a new concept for many candidates, so they may not find a solution in short time during interviews. In order to get some visual ideas about mirrors, we may draw a binary tree and its mirror according to our daily experience. For example, the binary tree on the right of Figure 1 is the mirror of the left one.
Figure 1: Two binary trees which are mirrors of each other 
Let us analyze these two trees in Figure 1 carefully to get the steps of mirrors. Their root nodes are identical, but their left and right children are swapped. Firstly we may swap two nodes under the root of the original binary tree, and it becomes the second tree in Figure 2.
Figure 2: Process to get mirror of a binary tree. (a) Swap children of the root node; (b) Swap children of the node 10; (c) Swap the children of node 6.

Now we can summarize the process for mirror: We visit all nodes in a binary tree with preorder traversal, and swap the children of current visited node if it has. We will get mirror of a binary tree after we visit all of its nodes.
Let us begin to write code after we get clear ideas about the process. The following is the sample code:
void Mirror(BinaryTreeNode *pNode)
{
if((pNode == NULL)  (pNode>m_pLeft == NULL && pNode>m_pRight))
return;
BinaryTreeNode *pTemp = pNode>m_pLeft;
pNode>m_pLeft = pNode>m_pRight;
pNode>m_pRight = pTemp;
if(pNode>m_pLeft)
MirrorRecursively(pNode>m_pLeft);
if(pNode>m_pRight)
MirrorRecursively(pNode>m_pRight);
}The discussion about this problem is included in my book <Coding Interviews: Questions, Analysis & Solutions>, with some revisions. You may find the details of this book on Amazon.com, or Apress.
The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages, please add a referenced to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact me (zhedahht@gmail.com) . Thanks.
Why are we not passing double pointer to root node
ReplyDeleteas we are trying to modify the root node(like we do in insert() fuction).Don't you think that the original root pointer will be unchanged by this mirror function?
The root node will not change when a tree gets mirrored.
Deletebut sir..when the left and right nodes of the root are changed,how are they reflected in the calling function since you are passing the root by value??
Deleteplease elaborate..
and since you are not returning anything,you can't even return the modified node and store it in the original root
Deleteusually you pass a pointers address that points to the root node. the root node by itself is a simple node in the tree. if you want to change what the pointer to the root node points to, in that case you need to pass the address of a pointer.
Deletevoid MirrorTree(TNode *root)
ReplyDelete{
stack st;
st.push(root);
while(!st.empty())
{
TNode *tempNode = st.top();
st.pop();
if (tempNode>left != NULL)
{
st.push(tempNode>left);
}
if (tempNode>right != NULL)
{
st.push(tempNode>right);
}
TNode *temp = tempNode>left;
tempNode>left = tempNode>right;
tempNode>right = temp;
}
}
Can I use C++ stack instead of recursion? Is my solution less efficient? Thank you for your guide!!
Can someone give me some practical usages of tree mirroing?
ReplyDeleteI mean the problems where mirroring the tree is the solution.
This question isn't tricky. I'd hope a candidate would have enough skill to recognize and code the solution within 20 minutes.
ReplyDeleteJava solution for those interested:
public void mirror() {
Stack stack = new Stack();
stack.add(this.root);
while (stack.size() > 0) {
BinaryTreeNode node = stack.pop();
if (node != null) {
stack.push(node.right);
stack.push(node.left);
//swap children.
BinaryTreeNode temp = node.left;
node.left = node.right;
node.right = temp;
}
}
}
it follows easily from the recursive definition i.e the mirror of a tree with three nodes is just head node with left and right subtree swapped.
ReplyDeleteBSTNode * copyTreeMirror(BSTNode * h){
if(h>left == 0 && h>right == 0){
return new BSTNode(h>value);
}
else
{
BSTNode * temp = new BSTNode(h>value);
if(h>left != 0)
temp>right = copyTreeMirror(h>left);
if(h>right != 0)
temp>left = copyTreeMirror(h>right);
return temp;
}
}
#include
ReplyDelete#include
struct node
{
struct node * left;
int data;
struct node * right;
};
void insert(struct node **root,int num)
{
if(*root==NULL)
{
*root=(struct node *) malloc(sizeof (struct node));
(*root)>data=num;
(*root)>left=NULL;
(*root)>right=NULL;
}
else
{
if(num<(*root)>data)
insert(&(*root)>left,num);
else
insert(&(*root)>right,num);
}
}
void inorder(struct node * root)
{
if(root==NULL)
return;
inorder(root>left);
printf("\n%d",root>data);
inorder(root>right);
}
void mirror(struct node **root)
{
struct node *temp;
if(*root==NULL)
return;
else
{
temp=(*root)>left;
(*root)>left=(*root)>right;
(*root)>right=temp;
}
mirror(&(*root)>left);
mirror(&(*root)>right);
}
void main()
{
struct node *root=NULL;
insert(&root,100);
insert(&root,90);
insert(&root,110);
insert(&root,95);
insert(&root,97);
insert(&root,50);
insert(&root,105);
insert(&root,102);
insert(&root,103);
insert(&root,115);
//inorder(root);
mirror(&root);
inorder(root);
}
java solution:
ReplyDeletepublic boolean mirrorEqual(Node left, Node right)
{
if (left == null  right==null)
return (left == null && right == null);
else
return left.key == right.key && mirrorEqual(left.leftChild, right.rightChild) && mirrorEqual(left.rightChild,right.leftChild);
}
video explanation Mirror of Tree's both method and code is discussed : www.youtube.com/watch?v=P40mZ4lWhA
ReplyDeletevideo explanation Mirror of Tree's both method and code is discussed : www.youtube.com/watch?v=P40mZ4lWhA
ReplyDelete