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.

13 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
  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