Description: Convert a binary tree into its mirror tree. A mirror tree of a binary tree is a tree with all of its left and right children interchanged.

 
If video does not load, Click here
 
Example:
 
Both trees below are mirrow trees of each other.

 

Algorithm and implementation:

 

The algorithm is as follows:

1)Convert left subtree into it’s mirror

2)Convert right subtree into it’s mirror

3)Exchange left and right pointers of the node being considered using a ‘temp’ pointer.

 

/*Let’s consider a function ‘convert’ used to convert a binary tree into its corresponding mirror tree*/

void convert(struct node* node)

{

 if (node==NULL) /*Empty*/

   return;

 

else

 {

   struct node* temp;

   convert(node->left);/*convert left subtree*/

   convert(node->right);/*convert right subtree*/

 

   temp  = node->right;/*exchange left and right pointers*/

   node->right  = node->left;

   node->left = temp;

 }

}

 

 

Time Complexity:

 

O(n), where 'n' is the number of nodes in the tree.

Go to top