Sunday, June 27, 2010

Code for Creating Mirror Image of a binary tree

MIRROR IMAGE:

We Have to Change a tree so that the roles of the left and right pointers are swapped at every node.
So the tree...
    4
   /  \
  2    5
 / \
1  3

is changed to...
    4
   / \
 5   2 //mirror image
     / \
    3   1
The solution is short, but very recursive. As it happens, this can be accomplished without changing the root node pointer, so the return-the-new-root construct is not necessary. Alternately, if you do not want to change the tree nodes, you may construct and return a new mirror tree based on the original tree.

Here is the code:

void mirror(struct node* node)
{
         if (node==NULL)
            return;
         else
            {
               struct node* temp;
               mirror(node->left);
               mirror(node->right);
               temp = node->left;
               node->left = node->right;
               node->right = temp;
              }
 }

2 comments:

Unknown said...

Can you do this without using recursion?

Dhinakaran said...

Ya we can do it without using recursion by using stack.