C++ Program to Create Mirror Image of a Binary Tree

This is a C++ Program for creating a mirror image of a binary tree using recursion.

Problem Description

We will be given a Tree and we have to create its mirror image and perform level order traversal on the tree before and after creating its mirror image. By doing a level order traversal, we will be able to verify the mirrored data easily (before and after the mirroring).

Expected Input and Output

Case 1. Balanced Tree: When the weight on both the sides of root is same.

                    25                   |                      25
                  /    \                 |                    /     \
                 27     19               |                  19      27
                / \     / \              |                 /  \    /  \
              17  91   13 55             |                55  13  91   17
 
             Input Tree                 Mirror           Output Tree

Case 2. Right Skewed Tree: When nodes at each and every level have just a right child.

         1                                   |                                  1
          \                                  |                                 /
           2                                 |                                2
            \                                |                               /
             3                               |                              3
              \                              |                             /
               4                             |                            4
                \                            |                           /
                 5                           |                          5
              Input Tree                   Mirror                    Output Tree

Case 3. Tree having just one node

advertisement
advertisement
              15                |              15
             Input Tree       Mirror        Output Tree
Problem Solution

For creating a mirror image of a tree, we need to traverse the subtrees. While traversing the subtrees we have to swap the left and the right child of all the nodes. After swapping the left and the right child of all the nodes the tree which we will obtain, will be the mirror image of the original tree which was taken as an input.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
Program/Source Code

Here is source code of the C++ Program for creating a Mirror Image of a given Binary Tree using Recursion. The program is successfully compiled and tested using Codeblocks gnu/gcc compiler on Windows 10. The program output is also shown below.

  1. /* C++ Program for creating the mirror image of a given Binary tree */
  2. #include<iostream>
  3. using namespace std;
  4. struct node
  5. {
  6.     int info;
  7.     struct node *left, *right;
  8. };
  9. class Tree
  10. {
  11.     public:
  12.         struct node *root;
  13.         struct node *createnode(int key);
  14.         void mirrorimage(struct node *root);
  15.         int heightoftree(struct node *root);
  16.         void currentlevel(struct node *root, int level);
  17.         Tree()
  18.         {
  19.             root = NULL;
  20.         }
  21. };
  22. /*
  23.  * Function to create new nodes.
  24.  */
  25. struct node *Tree :: createnode(int key)
  26. {
  27.     struct node *newnode = new node;
  28.     newnode->info = key;
  29.     newnode->left = NULL;
  30.     newnode->right = NULL;
  31.     return(newnode);
  32. }
  33. /*
  34.  * Function to swap left and right child of  a node for creating mirror image.
  35.  */
  36. void Tree :: mirrorimage(struct node *root)
  37. {
  38.   if (root != NULL)
  39.     {
  40.         struct node *temp;
  41.         /* first traversing the left subtree */
  42.         mirrorimage(root->left);
  43.         /* Traversing the right subtree. */      
  44.         mirrorimage(root->right);     
  45.         temp = root->left;         
  46.          /* 
  47.           * swap the left and the right child 
  48.           * of all the nodes to create
  49.           * a mirror image of a tree 
  50.           */
  51.         root->left  = root->right;  
  52.         root->right = temp;
  53.     }
  54. }
  55. /*
  56.  * Function to find the height of a tree.
  57.  */
  58. int Tree :: heightoftree(struct node *root)
  59. {
  60.     int maximum;
  61.     if (root!=NULL)
  62.     {
  63.         /* Finding the height of left subtree. */
  64.         int leftsubtree = heightoftree(root->left); 
  65.         /* Finding the height of right subtree. */
  66.         int rightsubtree = heightoftree(root->right);  
  67.         if (leftsubtree > rightsubtree)
  68.         {
  69.             maximum = leftsubtree + 1;
  70.             return maximum;
  71.         }
  72.         else
  73.         {
  74.             maximum = rightsubtree + 1;
  75.             return maximum;
  76.         }
  77.     }
  78. }
  79. /*
  80.  * Function to print all the nodes left to right of the current level
  81.  */
  82. void Tree :: currentlevel(struct node *root, int level)
  83. {
  84.     if (root != NULL)
  85.     {
  86.         if (level == 1)
  87.         {
  88.             cout<<root->info<<"\t";
  89.         }
  90.         else if (level > 1)
  91.         {
  92.             currentlevel(root->left, level-1);
  93.             currentlevel(root->right, level-1);
  94.         }
  95.     }
  96. }
  97. int main()
  98. {
  99.    /* Creating first Tree. */
  100.     Tree t;
  101.     struct node *newnode = t.createnode(25);
  102.     newnode->left = t.createnode(27);
  103.     newnode->right = t.createnode(19);
  104.     newnode->left->left = t.createnode(17);
  105.     newnode->left->right = t.createnode(91);
  106.     newnode->right->left = t.createnode(13);
  107.     newnode->right->right = t.createnode(55);
  108.     /* Sample Tree 1- Balanced Tree.
  109.      *               25                   |                      25
  110.      *             /    \                 |                    /     \
  111.      *            27     19               |                  19      27
  112.      *           / \     / \              |                 /  \    /  \
  113.      *         17  91   13 55             |                55  13  91   17
  114.      *           Input Tree              Mirror               Output Tree
  115.      */
  116.     cout<<"Level Order Traversal of Tree 1 before creating its mirror image is";
  117.     cout<<endl;
  118.     int i;
  119.     int height = t.heightoftree(newnode);
  120.      /* Printing nodes level by level */
  121.     for(i = 1; i <= height; i++)     
  122.     {
  123.         t.currentlevel(newnode,i);
  124.     }
  125.     cout<<"\n\nLevel Order Traversal of Tree 1 after creating its mirror image is";
  126.     cout<<endl;
  127.     height = t.heightoftree(newnode);
  128.     t.mirrorimage(newnode);
  129.     /* Printing nodes level by level */
  130.     for(i = 1; i <= height; i++)      
  131.     {
  132.         t.currentlevel(newnode,i);
  133.     }
  134.  
  135.     /* Creating second Tree. */
  136.     struct node *node = t.createnode(1);
  137.     node->right = t.createnode(2);
  138.     node->right->right = t.createnode(3);
  139.     node->right->right->right = t.createnode(4);
  140.     node->right->right->right->right = t.createnode(5);
  141.     /* Sample Tree 2-   Right Skewed Tree (Unbalanced).
  142.      *     1                                   |                        1
  143.      *      \                                  |                       /
  144.      *       2                                 |                      2
  145.      *        \                                |                     /
  146.      *         3                               |                    3
  147.      *          \                              |                   /
  148.      *           4                             |                  4
  149.      *            \                            |                 /
  150.      *             5                           |               5
  151.      *          Input Tree                   Mirror           Output Tree
  152.      */
  153.     cout<<endl;
  154.     cout<<"\nLevel Order Traversal of Tree 2 before creating its mirror image is";
  155.     cout<<endl;
  156.     height = t.heightoftree(node);
  157.     /* Printing nodes level by level */
  158.     for(i = 1; i <= height; i++) 
  159.     {
  160.         t.currentlevel(node,i);
  161.     }
  162.     cout<<endl;
  163.     cout<<"\nLevel Order Traversal of Tree 2 after creating its mirror image is";
  164.     cout<<endl;
  165.     height = t.heightoftree(node);
  166.     t.mirrorimage(node);
  167.     /* Printing nodes level by level */
  168.     for(i = 1; i <= height; i++) 
  169.     {
  170.         t.currentlevel(node,i);
  171.     }
  172.  
  173.     /* Creating  third tree having just one root node */
  174.     struct node *root = t.createnode(15);
  175.     /* Sample Tree 3 - Tree having just one root node.
  176.      *              15           |              15
  177.      *        Input Tree                      Output Tree
  178.      *                         Mirror
  179.      */
  180.     cout<<endl;
  181.     cout<<"\nLevel Order Traversal of Tree 3 before creating its mirror image is";
  182.     cout<<endl;
  183.     height = t.heightoftree(root);
  184.     /* Printing nodes level by level */
  185.     for(i = 1; i <= height; i++) 
  186.     {
  187.         t.currentlevel(root,i);
  188.     }
  189.     cout<<endl;
  190.     cout<<"\nLevel Order Traversal of Tree 3 after creating its mirror image is";
  191.     cout<<endl;
  192.     height = t.heightoftree(root);
  193.     t.mirrorimage(root);
  194.     /* Printing nodes level by level */
  195.     for(i = 1; i <= height; i++) 
  196.     {
  197.         t.currentlevel(root,i);
  198.     }
  199.     return 0;
  200. }
Program Explanation

1. Here in this program we have created a function called mirrorimage(struct node *root). The idea behind creating a mirror image is swapping the left and the right child of all the nodes from top to bottom.
2. In order to do that we need to traverse the nodes. So, we have used the post order traversal i.e. first we will visit all the nodes left to the root node then we will visit all the nodes right to the root node.
3. As the third step of Post Order traversal, instead of printing the value of nodes we have called swap function to swap the left and right child of a node.
4. We have used level order traversal to print the tree before and after creating its mirror image.

advertisement
Runtime Test Cases
Level Order Traversal of Tree 1 before creating its mirror image is
25      27      19      17      91      13      55
 
Level Order Traversal of Tree 1 after creating its mirror image is
25      19      27      55      13      91      17
 
Level Order Traversal of Tree 2 before creating its mirror image is
1       2       3       4       5
 
Level Order Traversal of Tree 2 after creating its mirror image is
1       2       3       4       5
 
Level Order Traversal of Tree 3 before creating its mirror image is
15
 
Level Order Traversal of Tree 3 after creating its mirror image is
15

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.
Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.

advertisement
If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.