Program to Create a Mirror Image of a Binary Tree

  • Write a C program to create a mirror image of a binary tree.
  • How to convert a binary tree to it's mirror image.

Given a binary tree, we have to create a new tree which is mirror image of given binary tree. A Mirror tree of a binary tree is also a binary tree with left and right pointer of every node interchanged. To create a mirror image of a binary tree, we have to first clone the tree and then swap left and right pointer of every node of tree. Below is the structure of binary tree node. 

struct node {
    int data;
    struct node *left;
    struct node *right;
};
Algorithm to create a mirror image of a tree
Let "root" be the root pointer of given binary tree.
  • If root is NULL, return NULL.
  • Create a new node and copy the data of root node to new node. Let the name if new node be newNode.
  • Recursively create mirror tree of left and right sub tree. let it be leftMirror and rightMirror.
  • Interchange left and right pointers. Assign leftMirror to right pointer and rightMirror to left pointer of newNode.
    • newNode->left = rightMirror.
    • newNode->right = leftMirror.
Time Complexity : O(n)

C program to create mirror tree of given binary tree

#include <stdio.h>
#include <limits.h>

struct node {
    int data;
    struct node *left;
    struct node *right;
};

struct node* getNewNode(int data) {
  /* dynamically allocate memory for a new node */ 
  struct node* newNode = (struct node*)malloc(sizeof(struct node));
 
  /* populate data in new Node */
  newNode->data = data;
  newNode->left = NULL;
  newNode->right = NULL;
  
  return newNode;
}

/*
This function returns below tree
            1
           / \
         9    12
        / \    \
       4  50    7
 
*/
struct node* generateBTree(){
    // Root Node
    struct node* root =  getNewNode(1);
 
    root->left = getNewNode(9);
    root->right = getNewNode(12);
 
    root->left->left = getNewNode(4);
    root->left->right = getNewNode(50);
    root->right->right = getNewNode(7);
    
    return root;
}

/* Returns a tree which is mirror image of passed tree 
by swapping left and right pointers */
struct node* getMirrorBinaryTree(struct node *root){
    if(root == NULL)
        return NULL;

    /* create a copy of root node */
    struct node* newNode = getNewNode(root->data);

    /* Recursively create clone of left and right sub tree 
    and swap them. Assign left subtree of original tree 
    to right pointer and right subtree to left pointer */
    newNode->right = getMirrorBinaryTree(root->left);
    newNode->left = getMirrorBinaryTree(root->right);

    /* Return root of mirrored tree */
    return newNode;
}

/*
 Prints inOrder Traversal of a binary tree
*/
void inOrderTraversal(struct node *nodeptr){
    if(nodeptr != NULL){
        /* Recursively prints in Order traversal of left sub-tree */
        inOrderTraversal(nodeptr->left);
        /* Prints current node */
        printf("%d ", nodeptr->data);
        /* Recursively prints in Order traversal of right sub-tree */
        inOrderTraversal(nodeptr->right);
    }
}
int main() {
    struct node *mirror, *root = generateBTree();    
    
    /*InOrder traversal of original tree */
    printf("Original Tree\n");
    inOrderTraversal(root);
    
    mirror = getMirrorBinaryTree(root);
    
    /*InOrder traversal of mirror tree */
    printf("\nMirror Tree\n");
    inOrderTraversal(mirror);
    
    getchar();
    return 0; 
}
Output
Original Tree
4 9 50 1 12 7
Mirror Tree
7 12 1 50 9 4
Posted by
Labels: