C Program to Create Mirror Image of 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.

Expected Input and Output

Case 1. If the input tree is a balanced tree. For example:

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

Case 2. If the tree has only right children at all the levels (Right Skewed Tree). A right skewed tree is one in which all the nodes just have a right child at all the levels. For example:

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

Case 3. Tree having just one node. For example:

 
              15                |              15
             Input Tree       Mirror        Output Tree

Problem Solution

1. For creating a mirror image of a tree, we need to traverse the subtrees.
2. While traversing the subtrees we have to swap the left and the right child of all the nodes.
3. 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.

Subscribe Now: Data Structures in C Newsletter | Important Subjects Newsletters

Program/Source Code

Here is source code of the C Program for creating a Mirror Image of a given 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.

/* C Program for creating the mirror image of a given tree.*/

```
#include <stdio.h>
```
```
#include <stdlib.h>
```
```
 
```
```
struct node
```
```
{
```
```
    int info;
```
```
    struct node* left, *right;
```
```
};
```
```
 
```
```
/*
```
```
 * Function to create new nodes.
```
```
 */
```
```
 
```
```
struct node* createnode(int key)
```
```
{
```

    struct node* newnode = (struct node*)malloc(sizeof(struct node));

```
    newnode->info = key;
```
```
    newnode->left = NULL;
```
```
    newnode->right = NULL;
```
```
 
```
```
    return(newnode);
```
```
}
```
```
 
```
```
/*
```

 *Function to swap left and right child of  a node for creating mirror image.

```
 */
```
```
 
```
```
void mirrorimage(struct node* root)
```
```
{
```
```
  if (root != NULL)
```
```
    {
```
```
        struct node* temp;
```

        /*first traversing the left subtree */

```
        mirrorimage(root->left);      
```

        /* Traversing the right subtree. */

```
        mirrorimage(root->right);     
```
```
 
```

        /* swap the left and right child of all the nodes to create

```
         * a mirror image of a tree
```
```
         */
```
```
 
```
```
        temp = root->left;
```
```
        root->left  = root->right;   
```
```
        root->right = temp;
```
```
 
```
```
    }
```
```
}
```
```
 
```
```
/*
```

 * Function to find the height of a tree.

```
 */
```
```
 
```
```
int heightoftree(struct node* root)
```
```
{
```
```
    int max;
```
```
 
```
```
    if (root!=NULL)
```
```
    {
```

        /*Finding the height of left subtree.*/

        int leftsubtree = heightoftree(root->left);

```
 
```

        /*Finding the height of right subtree.*/

        int rightsubtree = heightoftree(root->right);

```
 
```
```
 
```
```
        if (leftsubtree > rightsubtree)
```
```
        {
```
```
            max = leftsubtree + 1;
```
```
            return max;
```
```
        }
```
```
        else
```
```
        {
```
```
            max = rightsubtree + 1;
```
```
            return max;
```
```
        }
```
```
    }
```
```
}
```
```
 
```
```
/*
```

 * Function to print all the nodes left to right of the current level

```
 */
```
```
 
```

void currentlevel(struct node* root, int level)

```
{
```
```
    if (root != NULL)
```
```
    {
```
```
        if (level == 1)
```
```
        {
```
```
            printf("%d ", root->info);
```
```
        }
```
```
 
```
```
        else if (level > 1)
```
```
        {
```

            currentlevel(root->left, level-1);

            currentlevel(root->right, level-1);

```
        }
```
```
    }
```
```
 
```
```
}
```
```
 
```
```
int main()
```
```
{
```
```
   /* Creating first Tree.*/
```
```
 
```

    struct node *newnode = createnode(25);

```
    newnode->left = createnode(27);
```
```
    newnode->right = createnode(19);
```

    newnode->left->left = createnode(17);

    newnode->left->right = createnode(91);

    newnode->right->left = createnode(13);

    newnode->right->right = createnode(55);

```
 
```
```
    /* Sample Tree 1- Balanced Tree.
```
```
 
```
```
 
```

                    25                   |                      25

                  /    \                 |                    /     \

                 27     19               |                  19      27

                / \     / \              |                 /  \    /  \

              17  91   13 55             |                55  13  91   17

```
 
```

             Input Tree                 Mirror           Output Tree

```
    */
```
```
 
```

    printf("Level Order Traversal of Tree 1 "

           "before creating its mirror image is \n");

```
 
```
```
    int i;
```
```
    int height = heightoftree(newnode);
```
```
 
```

    /* calling current level function, by passing levels one by one

```
     * in an increasing order.
```
```
     */
```
```
 
```
```
    for(i = 1; i <= height; i++)      
```
```
    {
```
```
        currentlevel(newnode,i);
```
```
    }
```

    printf("\n\nLevel Order Traversal of Tree 1 "

               "after creating its mirror image is \n");

```
 
```
```
 
```
```
    height = heightoftree(newnode);
```
```
    mirrorimage(newnode);
```
```
 
```

   /* calling current level function, by passing levels one by one

```
    * in an increasing order.
```
```
    */
```
```
 
```
```
    for(i = 1; i <= height; i++)   
```
```
    {
```
```
        currentlevel(newnode,i);
```
```
    }
```
```
 
```
```
    /*Creating second Tree.*/
```
```
 
```
```
    struct node *node = createnode(1);
```
```
    node->right = createnode(2);
```
```
    node->right->right = createnode(3);
```

    node->right->right->right = createnode(4);

    node->right->right->right->right = createnode(5);

```
 
```

    /* Sample Tree 2-   Right Skewed Tree (Unbalanced).

```
 
```

      1                                   |                                  1

       \                                  |                                 /

        2                                 |                                2

         \                                |                               /

          3                               |                              3

           \                              |                             /

            4                             |                            4

             \                            |                           /

              5                           |                          5

```
 
```

           Input Tree                   Mirror                    Output Tree

```
    */  
```
```
 
```

    printf("\n\nLevel Order Traversal of Tree 2 "

               "before creating its mirror image is \n");

```
 
```
```
    height = heightoftree(node);
```
```
 
```

    /* calling current level function, by passing levels one by one

```
     * in an increasing order.
```
```
     */
```
```
 
```
```
    for(i = 1; i <= height; i++)
```
```
    {
```
```
        currentlevel(node,i);
```
```
    }
```
```
 
```

    printf("\n\nLevel Order Traversal of Tree 2 "

               "after creating its mirror image is \n");

```
 
```
```
    height = heightoftree(node);
```
```
    mirrorimage(node);
```
```
 
```

    /* calling current level function, by passing levels one by one

```
     * in an increasing order.
```
```
     */
```
```
 
```
```
    for(i = 1; i <= height; i++)      
```
```
    {
```
```
        currentlevel(node,i);
```
```
    }
```
```
 
```

    /* Creating  third tree having just one root node */

```
    struct node *root = createnode(15);
```
```
 
```
```
 
```
```
 
```

    /* Sample Tree 3 -   Tree having just one root node.

```
 
```

                   15           |              15

             Input Tree                      Output Tree

```
                              Mirror
```
```
    */
```
```
 
```

    printf("\n\nLevel Order Traversal of Tree 3 "

               "before creating its mirror image is \n");

```
    height = heightoftree(root);
```
```
 
```

    /* calling current level function, by passing levels one by one

```
     * in an increasing order.
```
```
     */
```
```
 
```
```
    for(i = 1; i <= height; i++)  
```
```
    {
```
```
        currentlevel(root,i);
```
```
    }
```
```
 
```

    printf("\n\nLevel Order Traversal of Tree 3 "

               "after creating its mirror image is \n");

```
    height = heightoftree(root);
```
```
    mirrorimage(root);
```
```
 
```

    /* calling current level function, by passing levels one by one

```
     * in an increasing order.
```
```
     */
```
```
 
```
```
    for(i = 1; i <= height; i++)
```
```
    {
```
```
        currentlevel(root,i);
```
```
    }
```
```
 
```
```
    return 0;
```
```
}
```

Program Explanation

1. Here in this program we have created a function called mirrorimage(struct node* root).
2. The idea behind creating a mirror image is swapping the left and the right child of all the nodes from top to bottom.
3. 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, and will swap both the children of a node one by one.

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

If you wish to look at programming examples on all topics, go to C Programming Examples.

« Prev - C Program to Find the Lowest Common Ancestor of a Binary Search Tree

» Next - C Program to Find the Height of Tree using Recursion

Related Posts:

Check Data Structure Books
Practice Design & Analysis of Algorithms MCQ
Check Computer Science Books
Practice Computer Science MCQs
Check Programming Books

Recommended Articles: