Jun 122012
 

Given a Binary Tree, write a function which will convert that tree to its Mirror Tree. For Example: If the Binary Tree is

       1
     /   \
    2     3
   / \
  4   5

Then the Mirror is

       1
     /   \
    3     2
         / \
        5   4

Solution:

As I have written in my earlier posts also, Tree problems are better solved using recursion (But recursion comes with its side effect). Finding the Mirror can also be visualized recursively.

Algorithm:

Step 1.  Compute Mirror of Left Sub-Tree
Step 2. Compute Mirror of Right Sub-Tree
Step 3. swap the left and right subtree values

Code:

    void mirrorTree(Node* root) 
    { 
        if (!root) 
            return;

        mirrorTree(root->lptr);
        mirrorTree(root->rptr); 

        // swap the left & right pointers
        Node* temp = root->lptr; 
        root->lptr = root->rptr;
        root->rptr = temp;
    }

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)