# 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
```