# Convert a Binary Tree into its Mirror Tree

Mirror of a Tree: Mirror of a Binary Tree T is another Binary Tree M(T) with left and right children of all non-leaf nodes interchanged. Trees in the above figure are mirror of each other

Method 1 (Recursive)

Algorithm – Mirror(tree):

```(1)  Call Mirror for left-subtree    i.e., Mirror(left-subtree)
(2)  Call Mirror for right-subtree  i.e., Mirror(right-subtree)
(3)  Swap left and right subtrees.
temp = left-subtree
left-subtree = right-subtree
right-subtree = temp
```

## C++

 `// C++ program to convert a binary tree ` `// to its mirror ` `#include ` `using` `namespace` `std; ` ` `  `/* A binary tree node has data, pointer  ` `to left child and a pointer to right child */` `struct` `Node  ` `{ ` `    ``int` `data; ` `    ``struct` `Node* left; ` `    ``struct` `Node* right; ` `}; ` ` `  `/* Helper function that allocates a new node with  ` `the given data and NULL left and right pointers. */` `struct` `Node* newNode(``int` `data) ` `{ ` `    ``struct` `Node* node = (``struct` `Node*) ` `                         ``malloc``(``sizeof``(``struct` `Node)); ` `    ``node->data = data; ` `    ``node->left = NULL; ` `    ``node->right = NULL; ` `     `  `    ``return``(node); ` `} ` ` `  ` `  `/* Change a tree so that the roles of the left and  ` `    ``right pointers are swapped at every node. ` ` `  `So the tree... ` `    ``4 ` `    ``/ ` `    ``2 5 ` `    ``/ ` `1 3 ` ` `  `is changed to... ` `    ``4 ` `    ``/ ` `    ``5 2 ` `        ``/ ` `    ``3 1 ` `*/` `void` `mirror(``struct` `Node* node)  ` `{ ` `    ``if` `(node == NULL)  ` `        ``return``;  ` `    ``else` `    ``{ ` `        ``struct` `Node* temp; ` `         `  `        ``/* do the subtrees */` `        ``mirror(node->left); ` `        ``mirror(node->right); ` `     `  `        ``/* swap the pointers in this node */` `        ``temp     = node->left; ` `        ``node->left = node->right; ` `        ``node->right = temp; ` `    ``} ` `}  ` ` `  `/* Helper function to print  ` `Inorder traversal.*/` `void` `inOrder(``struct` `Node* node)  ` `{ ` `    ``if` `(node == NULL)  ` `        ``return``; ` `     `  `    ``inOrder(node->left); ` `    ``cout << node->data << ``" "``; ` `    ``inOrder(node->right); ` `}  ` ` `  ` `  `// Driver Code ` `int` `main() ` `{ ` `    ``struct` `Node *root = newNode(1); ` `    ``root->left = newNode(2); ` `    ``root->right = newNode(3); ` `    ``root->left->left = newNode(4); ` `    ``root->left->right = newNode(5);  ` `     `  `    ``/* Print inorder traversal of the input tree */` `    ``cout << ``"Inorder traversal of the constructed"` `         ``<< ``" tree is"` `<< endl; ` `    ``inOrder(root); ` `     `  `    ``/* Convert tree to its mirror */` `    ``mirror(root);  ` `     `  `    ``/* Print inorder traversal of the mirror tree */` `    ``cout << ````" Inorder traversal of the mirror tree"``` `         ``<< ````" is "````;  ` `    ``inOrder(root); ` `     `  `    ``return` `0;  ` `} ` ` `  `// This code is contributed by Akanksha Rai `

## C

 `// C program to convert a binary tree ` `// to its mirror ` `#include ` `#include ` ` `  `/* A binary tree node has data, pointer  ` `   ``to left child and a pointer to right child */` `struct` `Node  ` `{ ` `    ``int` `data; ` `    ``struct` `Node* left; ` `    ``struct` `Node* right; ` `}; ` ` `  `/* Helper function that allocates a new node with the ` `   ``given data and NULL left and right pointers. */` `struct` `Node* newNode(``int` `data) ` ` `  `{ ` `  ``struct` `Node* node = (``struct` `Node*) ` `                       ``malloc``(``sizeof``(``struct` `Node)); ` `  ``node->data = data; ` `  ``node->left = NULL; ` `  ``node->right = NULL; ` `   `  `  ``return``(node); ` `} ` ` `  ` `  `/* Change a tree so that the roles of the  left and  ` `    ``right pointers are swapped at every node. ` ` `  ` ``So the tree... ` `       ``4 ` `      ``/ ` `     ``2   5 ` `    ``/ ` `   ``1   3 ` ` `  ` ``is changed to... ` `       ``4 ` `      ``/ ` `     ``5   2 ` `        ``/ ` `       ``3   1 ` `*/` `void` `mirror(``struct` `Node* node)  ` `{ ` `  ``if` `(node==NULL)  ` `    ``return``;   ` `  ``else`  `  ``{ ` `    ``struct` `Node* temp; ` `     `  `    ``/* do the subtrees */` `    ``mirror(node->left); ` `    ``mirror(node->right); ` ` `  `    ``/* swap the pointers in this node */` `    ``temp        = node->left; ` `    ``node->left  = node->right; ` `    ``node->right = temp; ` `  ``} ` `}  ` ` `  `/* Helper function to print Inorder traversal.*/` `void` `inOrder(``struct` `Node* node)  ` `{ ` `  ``if` `(node == NULL)  ` `    ``return``; ` `   `  `  ``inOrder(node->left); ` `  ``printf``(``"%d "``, node->data); ` `  ``inOrder(node->right); ` `}   ` ` `  ` `  `/* Driver program to test mirror() */` `int` `main() ` `{ ` `  ``struct` `Node *root = newNode(1); ` `  ``root->left        = newNode(2); ` `  ``root->right       = newNode(3); ` `  ``root->left->left  = newNode(4); ` `  ``root->left->right = newNode(5);  ` `   `  `  ``/* Print inorder traversal of the input tree */` `  ``printf``(``"Inorder traversal of the constructed"` `           ````" tree is "````); ` `  ``inOrder(root); ` `   `  `  ``/* Convert tree to its mirror */` `  ``mirror(root);  ` `   `  `  ``/* Print inorder traversal of the mirror tree */` `  ``printf``(````" Inorder traversal of the mirror tree"``` `         ````" is "````);   ` `  ``inOrder(root); ` `   `  `  ``return` `0;   ` `} `

## Java

 `// Java program to convert binary tree into its mirror ` ` `  `/* Class containing left and right child of current ` `   ``node and key value*/` `class` `Node ` `{ ` `    ``int` `data; ` `    ``Node left, right; ` ` `  `    ``public` `Node(``int` `item) ` `    ``{ ` `        ``data = item; ` `        ``left = right = ``null``; ` `    ``} ` `} ` ` `  `class` `BinaryTree ` `{ ` `    ``Node root; ` ` `  `    ``void` `mirror() ` `    ``{ ` `        ``root = mirror(root); ` `    ``} ` ` `  `    ``Node mirror(Node node) ` `    ``{ ` `        ``if` `(node == ``null``) ` `            ``return` `node; ` ` `  `        ``/* do the subtrees */` `        ``Node left = mirror(node.left); ` `        ``Node right = mirror(node.right); ` ` `  `        ``/* swap the left and right pointers */` `        ``node.left = right; ` `        ``node.right = left; ` ` `  `        ``return` `node; ` `    ``} ` ` `  `    ``void` `inOrder() ` `    ``{ ` `        ``inOrder(root); ` `    ``} ` ` `  `    ``/* Helper function to test mirror(). Given a binary ` `       ``search tree, print out its data elements in ` `       ``increasing sorted order.*/` `    ``void` `inOrder(Node node) ` `    ``{ ` `        ``if` `(node == ``null``) ` `            ``return``; ` ` `  `        ``inOrder(node.left); ` `        ``System.out.print(node.data + ``" "``); ` ` `  `        ``inOrder(node.right); ` `    ``} ` ` `  `    ``/* testing for example nodes */` `    ``public` `static` `void` `main(String args[]) ` `    ``{ ` `        ``/* creating a binary tree and entering the nodes */` `        ``BinaryTree tree = ``new` `BinaryTree(); ` `        ``tree.root = ``new` `Node(``1``); ` `        ``tree.root.left = ``new` `Node(``2``); ` `        ``tree.root.right = ``new` `Node(``3``); ` `        ``tree.root.left.left = ``new` `Node(``4``); ` `        ``tree.root.left.right = ``new` `Node(``5``); ` ` `  `        ``/* print inorder traversal of the input tree */` `        ``System.out.println(``"Inorder traversal of input tree is :"``); ` `        ``tree.inOrder(); ` `        ``System.out.println(``""``); ` ` `  `        ``/* convert tree to its mirror */` `        ``tree.mirror(); ` ` `  `        ``/* print inorder traversal of the minor tree */` `        ``System.out.println(``"Inorder traversal of binary tree is : "``); ` `        ``tree.inOrder(); ` ` `  `    ``} ` `} `

## Python3

 `# Python3 program to convert a binary  ` `# tree to its mirror ` ` `  `# Utility function to create a new ` `# tree node  ` `class` `newNode: ` `    ``def` `__init__(``self``,data): ` `        ``self``.data ``=` `data ` `        ``self``.left ``=` `self``.right ``=` `None` ` `  `""" Change a tree so that the roles of the  ` `    ``left and right pointers are swapped at ` `    ``every node.  ` ` `  `So the tree...  ` `        ``4  ` `        ``/   ` `    ``2 5  ` `    ``/   ` `    ``1 3  ` ` `  `is changed to...  ` `    ``4  ` `    ``/   ` `    ``5 2  ` `    ``/   ` `    ``3 1  ` `"""` `def` `mirror(node):  ` ` `  `    ``if` `(node ``=``=` `None``): ` `        ``return` `    ``else``: ` ` `  `        ``temp ``=` `node  ` `         `  `        ``""" do the subtrees """` `        ``mirror(node.left)  ` `        ``mirror(node.right)  ` ` `  `        ``""" swap the pointers in this node """` `        ``temp ``=` `node.left  ` `        ``node.left ``=` `node.right  ` `        ``node.right ``=` `temp  ` ` `  `""" Helper function to print Inorder traversal."""` `def` `inOrder(node) : ` ` `  `    ``if` `(node ``=``=` `None``):  ` `        ``return` `         `  `    ``inOrder(node.left)  ` `    ``print``(node.data, end ``=` `" "``)  ` `    ``inOrder(node.right)  ` ` `  `# Driver code  ` `if` `__name__ ``=``=``"__main__"``:  ` ` `  `    ``root ``=` `newNode(``1``)  ` `    ``root.left ``=` `newNode(``2``)  ` `    ``root.right ``=` `newNode(``3``)  ` `    ``root.left.left ``=` `newNode(``4``)  ` `    ``root.left.right ``=` `newNode(``5``)  ` ` `  `    ``""" Print inorder traversal of ` `        ``the input tree """` `    ``print``(``"Inorder traversal of the"``,  ` `               ``"constructed tree is"``)  ` `    ``inOrder(root)  ` `     `  `    ``""" Convert tree to its mirror """` `    ``mirror(root)  ` ` `  `    ``""" Print inorder traversal of  ` `        ``the mirror tree """` `    ``print``(````" Inorder traversal of"````,  ` `              ``"the mirror treeis "``)  ` `    ``inOrder(root)  ` ` `  `# This code is contributed by ` `# Shubham Singh(SHUBHAMSINGH10) `

## C#

 `// C# program to convert binary  ` `// tree into its mirror  ` `using` `System; ` ` `  `// Class containing left and right  ` `// child of current node and key value ` `public` `class` `Node ` `{ ` `    ``public` `int` `data; ` `    ``public` `Node left, right; ` ` `  `    ``public` `Node(``int` `item) ` `    ``{ ` `        ``data = item; ` `        ``left = right = ``null``; ` `    ``} ` `} ` ` `  `class` `GFG ` `{ ` `public` `Node root; ` ` `  `public` `virtual` `void` `mirror() ` `{ ` `    ``root = mirror(root); ` `} ` ` `  `public` `virtual` `Node mirror(Node node) ` `{ ` `    ``if` `(node == ``null``) ` `    ``{ ` `        ``return` `node; ` `    ``} ` ` `  `    ``/* do the subtrees */` `    ``Node left = mirror(node.left); ` `    ``Node right = mirror(node.right); ` ` `  `    ``/* swap the left and right pointers */` `    ``node.left = right; ` `    ``node.right = left; ` ` `  `    ``return` `node; ` `} ` ` `  `public` `virtual` `void` `inOrder() ` `{ ` `    ``inOrder(root); ` `} ` ` `  `/* Helper function to test mirror().  ` `Given a binary search tree, print out its  ` `data elements in increasing sorted order.*/` `public` `virtual` `void` `inOrder(Node node) ` `{ ` `    ``if` `(node == ``null``) ` `    ``{ ` `        ``return``; ` `    ``} ` ` `  `    ``inOrder(node.left); ` `    ``Console.Write(node.data + ``" "``); ` ` `  `    ``inOrder(node.right); ` `} ` ` `  `/* testing for example nodes */` `public` `static` `void` `Main(``string``[] args) ` `{ ` `    ``/* creating a binary tree and  ` `    ``entering the nodes */` `    ``GFG tree = ``new` `GFG(); ` `    ``tree.root = ``new` `Node(1); ` `    ``tree.root.left = ``new` `Node(2); ` `    ``tree.root.right = ``new` `Node(3); ` `    ``tree.root.left.left = ``new` `Node(4); ` `    ``tree.root.left.right = ``new` `Node(5); ` ` `  `    ``/* print inorder traversal of the input tree */` `    ``Console.WriteLine(``"Inorder traversal "` `+  ` `                      ``"of input tree is :"``); ` `    ``tree.inOrder(); ` `    ``Console.WriteLine(``""``); ` ` `  `    ``/* convert tree to its mirror */` `    ``tree.mirror(); ` ` `  `    ``/* print inorder traversal of the minor tree */` `    ``Console.WriteLine(``"Inorder traversal "` `+  ` `                    ``"of binary tree is : "``); ` `    ``tree.inOrder(); ` `} ` `} ` ` `  `// This code is contributed by Shrikant13 `

Output :

```Inorder traversal of the constructed tree is
4 2 5 1 3
Inorder traversal of the mirror tree is
3 1 5 2 4 ```

Time & Space Complexities: This program is similar to traversal of tree space and time complexities will be same as Tree traversal (Please see our Tree Traversal post for details)

Method 2 (Iterative)

The idea is to do queue based level order traversal. While doing traversal, swap left and right children of every node.

 `// Iterative CPP program to convert a Binary ` `// Tree to its mirror ` `#include ` `using` `namespace` `std; ` ` `  `/* A binary tree node has data, pointer to ` `   ``left child and a pointer to right child */` `struct` `Node ` `{ ` `    ``int` `data; ` `    ``struct` `Node* left; ` `    ``struct` `Node* right; ` `}; ` ` `  `/* Helper function that allocates a new node ` `   ``with the given data and NULL left and right ` `   ``pointers. */` `struct` `Node* newNode(``int` `data) ` ` `  `{ ` `    ``struct` `Node* node = ``new` `Node; ` `    ``node->data = data; ` `    ``node->left = node->right = NULL; ` `    ``return``(node); ` `} ` ` `  `/* Change a tree so that the roles of the  left and ` `    ``right pointers are swapped at every node. ` ` ``So the tree... ` `       ``4 ` `      ``/ ` `     ``2   5 ` `    ``/ ` `   ``1   3 ` ` `  ` ``is changed to... ` `       ``4 ` `      ``/ ` `     ``5   2 ` `        ``/ ` `       ``3   1 ` `*/` `void` `mirror(Node* root) ` `{ ` `    ``if` `(root == NULL) ` `        ``return``; ` ` `  `    ``queue q; ` `    ``q.push(root); ` ` `  `    ``// Do BFS. While doing BFS, keep swapping ` `    ``// left and right children ` `    ``while` `(!q.empty()) ` `    ``{ ` `        ``// pop top node from queue ` `        ``Node* curr = q.front(); ` `        ``q.pop(); ` ` `  `        ``// swap left child with right child ` `        ``swap(curr->left, curr->right); ` ` `  `        ``// push left and right children ` `        ``if` `(curr->left) ` `            ``q.push(curr->left); ` `        ``if` `(curr->right) ` `            ``q.push(curr->right); ` `    ``} ` `} ` ` `  ` `  `/* Helper function to print Inorder traversal.*/` `void` `inOrder(``struct` `Node* node) ` `{ ` `    ``if` `(node == NULL) ` `        ``return``; ` `    ``inOrder(node->left); ` `    ``cout << node->data << ``" "``; ` `    ``inOrder(node->right); ` `} ` ` `  ` `  `/* Driver program to test mirror() */` `int` `main() ` `{ ` `    ``struct` `Node *root = newNode(1); ` `    ``root->left        = newNode(2); ` `    ``root->right       = newNode(3); ` `    ``root->left->left  = newNode(4); ` `    ``root->left->right = newNode(5); ` ` `  `    ``/* Print inorder traversal of the input tree */` `    ``cout << ````" Inorder traversal of the"``` `            ````" constructed tree is "````; ` `    ``inOrder(root); ` ` `  `    ``/* Convert tree to its mirror */` `    ``mirror(root); ` ` `  `    ``/* Print inorder traversal of the mirror tree */` `    ``cout << ````" Inorder traversal of the "``` `           ````"mirror tree is "````; ` `    ``inOrder(root); ` ` `  `    ``return` `0; ` `} `

This article is attributed to GeeksforGeeks.org

code

load comments