Convert a Binary Tree into its Mirror Tree (Invert Binary Tree)
Given a binary tree, the task is to convert the binary tree into its Mirror tree. Mirror of a Binary Tree T is another Binary Tree M(T) with left and right children of all non-leaf nodes interchanged.
The idea is to traverse recursively and swap the right and left subtrees after traversing the subtrees.
Follow the steps below to solve the problem:
- Call Mirror for left-subtree i.e., Mirror(left-subtree)
- Call Mirror for right-subtree i.e., Mirror(right-subtree)
- Swap left and right subtrees.
- temp = left-subtree
- left-subtree = right-subtree
- right-subtree = temp
Below is the implementation of the above approach:
C++
// C++ program to convert a binary tree // to its mirror #include <bits/stdc++.h> 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 / \ 3 1 is changed to... 4 / \ 5 2 / \ 1 3 */ 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 << "\nInorder traversal of the mirror tree" << " is \n" ; inOrder(root); return 0; } // This code is contributed by Akanksha Rai |
C
// C program to convert a binary tree // to its mirror #include <stdio.h> #include <stdlib.h> /* 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 \n" ); inOrder(root); /* Convert tree to its mirror */ mirror(root); /* Print inorder traversal of the mirror tree */ printf ( "\nInorder traversal of the mirror tree" " is \n" ); 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 the constructed 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 the mirror 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 ( "\nInorder traversal of" , "the mirror tree is " ) 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 the constructed 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 the mirror tree is" ); tree.inOrder(); } } // This code is contributed by Shrikant13 |
Javascript
<script> // JavaScript program to convert // binary tree into its mirror /* Class containing left and right child of current node and key value*/ class Node { constructor(item) { this .data=item; this .left= this .right= null ; } } let root; function mirror(node) { if (node == null ) return node; /* do the subtrees */ let left = mirror(node.left); let right = mirror(node.right); /* swap the left and right pointers */ node.left = right; node.right = left; return node; } /* Helper function to test mirror(). Given a binary search tree, print out its data elements in increasing sorted order.*/ function inOrder(node) { if (node == null ) return ; inOrder(node.left); document.write(node.data + " " ); inOrder(node.right); } /* testing for example nodes */ /* creating a binary tree and entering the nodes */ root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); /* print inorder traversal of the input tree */ document.write( "Inorder traversal of input tree is :<br>" ); inOrder(root); document.write( "<br>" ); /* convert tree to its mirror */ mirror(root); /* print inorder traversal of the minor tree */ document.write( "Inorder traversal of binary tree is : <br>" ); inOrder(root); // This code is contributed by rag2127 </script> |
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 Complexity: O(N), Visiting all the nodes of the tree of size N
Auxiliary Space: O(N), For function call stack space
Convert a Binary Tree into its Mirror Tree using Level Order Traversal:
The idea is to do queue-based level order traversal. While doing traversal, swap left and right children of every node.
Follow the steps below to solve the problem:
- Perform the level order traversal
- While traversing over the tree swap the left and right child of current node
Below is the implementation of the above approach:
C++
// Iterative CPP program to convert a Binary // Tree to its mirror #include <bits/stdc++.h> 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<Node*> 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 \n" ; inOrder(root); /* Convert tree to its mirror */ mirror(root); /* Print inorder traversal of the mirror tree */ cout << "\nInorder traversal of the " "mirror tree is \n" ; inOrder(root); return 0; } |
Java
// Iterative Java program to convert a Binary // Tree to its mirror import java.util.*; class GFG { /* A binary tree node has data, pointer to left child and a pointer to right child */ static class Node { int data; Node left; Node right; }; /* Helper function that allocates a new node with the given data and null left and right pointers. */ static Node newNode( int data) { 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 */ static void mirror(Node root) { if (root == null ) return ; Queue<Node> q = new LinkedList<>(); q.add(root); // Do BFS. While doing BFS, keep swapping // left and right children while (q.size() > 0 ) { // pop top node from queue Node curr = q.peek(); q.remove(); // swap left child with right child Node temp = curr.left; curr.left = curr.right; curr.right = temp; // push left and right children if (curr.left != null ) q.add(curr.left); if (curr.right != null ) q.add(curr.right); } } /* Helper function to print Inorder traversal.*/ static void inOrder(Node node) { if (node == null ) return ; inOrder(node.left); System.out.print(node.data + " " ); inOrder(node.right); } /* Driver code */ public static void main(String args[]) { 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 */ System.out.print( "Inorder traversal of the" + " constructed tree is \n" ); inOrder(root); /* Convert tree to its mirror */ mirror(root); /* Print inorder traversal of the mirror tree */ System.out.print( "\nInorder traversal of the " + "mirror tree is \n" ); inOrder(root); } } // This code is contributed by Arnab Kundu |
Python3
# Python3 program to convert a Binary # Tree to its mirror # A binary tree node has data, pointer to # left child and a pointer to right child # Helper function that allocates a new node # with the given data and None left and # right pointers class newNode: def __init__( self , data): self .data = data self .left = None 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(root): if (root = = None ): return q = [] q.append(root) # Do BFS. While doing BFS, keep swapping # left and right children while ( len (q)): # pop top node from queue curr = q[ 0 ] q.pop( 0 ) # swap left child with right child curr.left, curr.right = curr.right, curr.left # append left and right children if (curr.left): q.append(curr.left) if (curr.right): q.append(curr.right) """ 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 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 ( "\nInorder traversal of the mirror tree is" ) inOrder(root) # This code is contributed by SHUBHAMSINGH10 |
C#
// C# Iterative Java program to convert a Binary // Tree to its mirror using System.Collections.Generic; using System; class GFG { /* A binary tree node has data, pointer to left child and a pointer to right child */ public class Node { public int data; public Node left; public Node right; }; /* Helper function that allocates a new node with the given data and null left and right pointers. */ static Node newNode( int data) { 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 */ static void mirror(Node root) { if (root == null ) return ; Queue<Node> q = new Queue<Node>(); q.Enqueue(root); // Do BFS. While doing BFS, keep swapping // left and right children while (q.Count > 0) { // pop top node from queue Node curr = q.Peek(); q.Dequeue(); // swap left child with right child Node temp = curr.left; curr.left = curr.right; curr.right = temp; ; // push left and right children if (curr.left != null ) q.Enqueue(curr.left); if (curr.right != null ) q.Enqueue(curr.right); } } /* Helper function to print Inorder traversal.*/ static void inOrder(Node node) { if (node == null ) return ; inOrder(node.left); Console.Write(node.data + " " ); inOrder(node.right); } /* Driver code */ public static void Main(String[] args) { 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 */ Console.Write( "Inorder traversal of the" + " constructed tree is \n" ); inOrder(root); /* Convert tree to its mirror */ mirror(root); /* Print inorder traversal of the mirror tree */ Console.Write( "\nInorder traversal of the " + "mirror tree is \n" ); inOrder(root); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Iterative Javascript program to convert a Binary // Tree to its mirror class Node { constructor(data) { this .left = null ; this .right = null ; this .data = data; } } /* Helper function that allocates a new node with the given data and null left and right pointers. */ function newNode(data) { let node = new Node(data); 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 */ function mirror(root) { if (root == null ) return ; let q = []; q.push(root); // Do BFS. While doing BFS, keep swapping // left and right children while (q.length > 0) { // pop top node from queue let curr = q[0]; q.shift(); // swap left child with right child let temp = curr.left; curr.left = curr.right; curr.right = temp;; // push left and right children if (curr.left != null ) q.push(curr.left); if (curr.right != null ) q.push(curr.right); } } /* Helper function to print Inorder traversal.*/ function inOrder(node) { if (node == null ) return ; inOrder(node.left); document.write( node.data + " " ); inOrder(node.right); } let 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 */ document.write( " Inorder traversal of the" + " constructed tree is " + "</br>" ); inOrder(root); /* Convert tree to its mirror */ mirror(root); /* Print inorder traversal of the mirror tree */ document.write( "</br>" + " Inorder traversal of the " + "mirror tree is " + "</br>" ); inOrder(root); </script> |
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 Complexity: O(N), Traversing over the tree of size N
Auxiliary Space: O(N), Using queue to store the nodes of the tree
Contact Us