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<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 / 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<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
" ); 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<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
" ; 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; } |
leave a comment
0 Comments