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 pre-order 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!!
Hi Harry,
DeleteInteresting piece! Great to see someone write Mirror of Binary Trees who is not a fanatic or a complete skeptic.
I enjoy reading the various AWS blogs and staying up to date with new offerings and best practices. I typically go to the root of the blog site and check the "Latest Posts" section at the bottom.
It looks like the "Latest Posts" section stopped updating about 2 weeks ago on April 20th. It would be very helpful if this could be fixed since this was very useful.
Excellent tutorials - very easy to understand with all the details. I hope you will continue to provide more such tutorials.
Merci Beaucoup,
Kevin
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=P40mZ4lWh-A
ReplyDeletevideo explanation Mirror of Tree's both method and code is discussed : www.youtube.com/watch?v=P40mZ4lWh-A
ReplyDeleteSalve
ReplyDeleteInteresting piece!Great to see someone write No. 12 - Mirror of Binary Trees who is not a fanatic or a complete skeptic.
I enjoy reading the various AWS blogs and staying up to date with new offerings and best practices. I typically go to the root of the blog site and check the "Latest Posts" section at the bottom.
It looks like the "Latest Posts" section stopped updating about 2 weeks ago on April 20th. AWS Training It would be very helpful if this could be fixed since this was very useful.
Excellent tutorials - very easy to understand with all the details. I hope you will continue to provide more such tutorials.
Merci Beaucoup,
Irene Hynes
Hi There,
ReplyDeleteInteresting piece! Great to see someone write No. 12 - Mirror of Binary Trees who is not a fanatic or a complete skeptic.
I enjoy reading the various AWS blogs and staying up to date with new offerings and best practices. I typically go to the root of the blog site and check the "Latest Posts" section at the bottom. AWS Training
It looks like the "Latest Posts" section stopped updating about 2 weeks ago on April 20th. It would be very helpful if this could be fixed since this was very useful.
Excellent tutorials - very easy to understand with all the details. I hope you will continue to provide more such tutorials.
Merci Beaucoup,
Radhey
Pleasant short https://collegepaperwritingservice-reviews.com/customwriting-com-review/ article, thanks to the details. It is very comprehensive data
ReplyDelete