Sunday, October 23, 2011

No. 12 - Mirror of Binary Trees


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.
We can notice that the children nodes of not 10 and 6 keep unchanged. Therefore, we need to continue to swap their children nodes. The third and fourth trees in Figure 2 are the swapped binary trees accordingly. It is noticeable that the fourth tree is the mirror target.

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.

18 comments:

  1. Why are we not passing double pointer to root node
    as 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?

    ReplyDelete
    Replies
    1. The root node will not change when a tree gets mirrored.

      Delete
    2. but 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??
      please elaborate..

      Delete
    3. and since you are not returning anything,you can't even return the modified node and store it in the original root

      Delete
    4. usually 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.

      Delete
  2. void MirrorTree(TNode *root)
    {
    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!!

    ReplyDelete
    Replies
    1. Hi Harry,

      Interesting 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

      Delete
  3. Can someone give me some practical usages of tree mirroing?
    I mean the problems where mirroring the tree is the solution.

    ReplyDelete
  4. This question isn't tricky. I'd hope a candidate would have enough skill to recognize and code the solution within 20 minutes.

    Java 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;
    }
    }
    }

    ReplyDelete
  5. 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.

    BSTNode * 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;
    }


    }

    ReplyDelete
  6. #include
    #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);



    }

    ReplyDelete
  7. java solution:
    public 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);
    }

    ReplyDelete
  8. video explanation Mirror of Tree's both method and code is discussed : www.youtube.com/watch?v=P40mZ4lWh-A

    ReplyDelete
  9. video explanation Mirror of Tree's both method and code is discussed : www.youtube.com/watch?v=P40mZ4lWh-A

    ReplyDelete
  10. The correlation-calculator displays correlations for major, exotic and cross currency pairs. It is a useful analytical tool that helps in making a sound trading decision.

    ReplyDelete
  11. Salve


    Interesting 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

    ReplyDelete
  12. Hi There,

    Interesting 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

    ReplyDelete