Given a binary tree, the task is to create a new binary tree which is a mirror image of the given binary tree.
Examples:
Input:
5
/ \
3 6
/ \
2 4
Output:
Inorder of original tree: 2 3 4 5 6
Inorder of mirror tree: 6 5 4 3 2
Mirror tree will be:
5
/ \
6 3
/ \
4 2
Input:
2
/ \
1 8
/ \
12 9
Output:
Inorder of original tree: 12 1 2 8 9
Inorder of mirror tree: 9 8 2 1 12
Approach: Write a recursive function that will take two nodes as the argument, one of the original tree and the other of the newly created tree. Now, for every passed node of the original tree, create a corresponding node in the mirror tree and then recursively call the same method for the child nodes but passing the left child of the original tree node with the right child of the mirror tree node and the right child of the original tree node with the left child of the mirror tree node.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <iostream>using namespace std;// A binary tree node has data, pointer to// left child and a pointer to right childtypedef struct treenode { int val; struct treenode* left; struct treenode* right;} node;// Helper function that allocates a new node with the// given data and NULL left and right pointersnode* createNode(int val){ node* newNode = (node*)malloc(sizeof(node)); newNode->val = val; newNode->left = NULL; newNode->right = NULL; return newNode;}// Helper function to print Inorder traversalvoid inorder(node* root){ if (root == NULL) return; inorder(root->left); cout <<" "<< root->val; inorder(root->right);}// mirrorify function takes two trees,// original tree and a mirror tree// It recurses on both the trees,// but when original tree recurses on left,// mirror tree recurses on right and// vice-versavoid mirrorify(node* root, node** mirror){ if (root == NULL) { mirror = NULL; return; } // Create new mirror node from original tree node *mirror = createNode(root->val); mirrorify(root->left, &((*mirror)->right)); mirrorify(root->right, &((*mirror)->left));}// Driver codeint main(){ node* tree = createNode(5); tree->left = createNode(3); tree->right = createNode(6); tree->left->left = createNode(2); tree->left->right = createNode(4); // Print inorder traversal of the input tree cout <<"Inorder of original tree: "; inorder(tree); node* mirror = NULL; mirrorify(tree, &mirror); // Print inorder traversal of the mirror tree cout <<"\nInorder of mirror tree: "; inorder(mirror); return 0;}// This code is contributed by shivanisinghss2110 |
C
// C implementation of the approach#include <malloc.h>#include <stdio.h>// A binary tree node has data, pointer to// left child and a pointer to right childtypedef struct treenode { int val; struct treenode* left; struct treenode* right;} node;// Helper function that allocates a new node with the// given data and NULL left and right pointersnode* createNode(int val){ node* newNode = (node*)malloc(sizeof(node)); newNode->val = val; newNode->left = NULL; newNode->right = NULL; return newNode;}// Helper function to print Inorder traversalvoid inorder(node* root){ if (root == NULL) return; inorder(root->left); printf("%d ", root->val); inorder(root->right);}// mirrorify function takes two trees,// original tree and a mirror tree// It recurses on both the trees,// but when original tree recurses on left,// mirror tree recurses on right and// vice-versavoid mirrorify(node* root, node** mirror){ if (root == NULL) { mirror = NULL; return; } // Create new mirror node from original tree node *mirror = createNode(root->val); mirrorify(root->left, &((*mirror)->right)); mirrorify(root->right, &((*mirror)->left));}// Driver codeint main(){ node* tree = createNode(5); tree->left = createNode(3); tree->right = createNode(6); tree->left->left = createNode(2); tree->left->right = createNode(4); // Print inorder traversal of the input tree printf("Inorder of original tree: "); inorder(tree); node* mirror = NULL; mirrorify(tree, &mirror); // Print inorder traversal of the mirror tree printf("\nInorder of mirror tree: "); inorder(mirror); return 0;} |
Java
// Java implementation of the approach import java.util.Comparator;class GFG{// A binary tree node has data, pointer to // left child and a pointer to right child static class node { int val; node left; node right; } // Helper function that allocates // a new node with the given data // and null left and right pointers static node createNode(int val) { node newNode = new node(); newNode.val = val; newNode.left = null; newNode.right = null; return newNode; } // Helper function to print Inorder traversal static void inorder(node root) { if (root == null) return; inorder(root.left); System.out.print(root.val); inorder(root.right); } // mirrorify function takes two trees, // original tree and a mirror tree // It recurses on both the trees, // but when original tree recurses on left, // mirror tree recurses on right and // vice-versa static node mirrorify(node root) { if (root == null) { return null; } // Create new mirror node from original tree node node mirror = createNode(root.val); mirror.right = mirrorify(root.left); mirror.left = mirrorify(root.right); return mirror;} // Driver code public static void main(String args[]){ node tree = createNode(5); tree.left = createNode(3); tree.right = createNode(6); tree.left.left = createNode(2); tree.left.right = createNode(4); // Print inorder traversal of the input tree System.out.print("Inorder of original tree: "); inorder(tree); node mirror = null; mirror = mirrorify(tree); // Print inorder traversal of the mirror tree System.out.print("\nInorder of mirror tree: "); inorder(mirror); } }// This code is contributed by Arnab Kundu |
Python3
# Python3 implementation of the approach# A binary tree node has data, # pointer to left child and # a pointer to right child # Linked list node class Node: def __init__(self, data): self.data = data self.left = None self.right = None# Helper function that allocates # a new node with the given data # and None left and right pointersdef createNode(val): newNode = Node(0) newNode.val = val newNode.left = None newNode.right = None return newNode# Helper function to print Inorder traversaldef inorder(root): if (root == None): return inorder(root.left) print( root.val, end = " ") inorder(root.right)# mirrorify function takes two trees,# original tree and a mirror tree# It recurses on both the trees,# but when original tree recurses on left,# mirror tree recurses on right and# vice-versadef mirrorify(root, mirror): if (root == None) : mirror = None return mirror # Create new mirror node # from original tree node mirror = createNode(root.val) mirror.right = mirrorify(root.left, ((mirror).right)) mirror.left = mirrorify(root.right, ((mirror).left)) return mirror# Driver Code if __name__=='__main__': tree = createNode(5) tree.left = createNode(3) tree.right = createNode(6) tree.left.left = createNode(2) tree.left.right = createNode(4) # Print inorder traversal of the input tree print("Inorder of original tree: ") inorder(tree) mirror = None mirror = mirrorify(tree, mirror) # Print inorder traversal of the mirror tree print("\nInorder of mirror tree: ") inorder(mirror)# This code is contributed by Arnab Kundu |
C#
// c# implementation of the approach using System;public class GFG{// A binary tree node has data, pointer to // left child and a pointer to right child public class node{ public int val; public node left; public node right;}// Helper function that allocates // a new node with the given data // and null left and right pointers public static node createNode(int val){ node newNode = new node(); newNode.val = val; newNode.left = null; newNode.right = null; return newNode;}// Helper function to print Inorder traversal public static void inorder(node root){ if (root == null) { return; } inorder(root.left); Console.Write("{0:D} ", root.val); inorder(root.right);}// mirrorify function takes two trees, // original tree and a mirror tree // It recurses on both the trees, // but when original tree recurses on left, // mirror tree recurses on right and // vice-versa public static node mirrorify(node root){ if (root == null) { return null; } // Create new mirror node from original tree node node mirror = createNode(root.val); mirror.right = mirrorify(root.left); mirror.left = mirrorify(root.right); return mirror;}// Driver code public static void Main(string[] args){ node tree = createNode(5); tree.left = createNode(3); tree.right = createNode(6); tree.left.left = createNode(2); tree.left.right = createNode(4); // Print inorder traversal of the input tree Console.Write("Inorder of original tree: "); inorder(tree); node mirror = null; mirror = mirrorify(tree); // Print inorder traversal of the mirror tree Console.Write("\nInorder of mirror tree: "); inorder(mirror);}} |
Javascript
<script>// Javascript implementation of the approach// A binary tree node has data, pointer to// left child and a pointer to right childclass node{ constructor() { this.val=0; this.left=this.right=null; }}// Helper function that allocates// a new node with the given data// and null left and right pointersfunction createNode(val){ let newNode = new node(); newNode.val = val; newNode.left = null; newNode.right = null; return newNode;}// Helper function to print Inorder traversalfunction inorder(root){ if (root == null) return; inorder(root.left); document.write(root.val+" "); inorder(root.right);}// mirrorify function takes two trees,// original tree and a mirror tree// It recurses on both the trees,// but when original tree recurses on left,// mirror tree recurses on right and// vice-versafunction mirrorify(root){ if (root == null) { return null; } // Create new mirror node from original tree node let mirror = createNode(root.val); mirror.right = mirrorify(root.left); mirror.left = mirrorify(root.right); return mirror;}// Driver codelet tree = createNode(5);tree.left = createNode(3);tree.right = createNode(6);tree.left.left = createNode(2);tree.left.right = createNode(4);// Print inorder traversal of the input treedocument.write("Inorder of original tree: ");inorder(tree);let mirror = null;mirror = mirrorify(tree);// Print inorder traversal of the mirror treedocument.write("<br>Inorder of mirror tree: ");inorder(mirror);// This code is contributed by avanitrachhadiya2155</script> |
Output
Inorder of original tree: 2 3 4 5 6 Inorder of mirror tree: 6 5 4 3 2
Time Complexity: O(n), where n is the number of nodes in the tree. This is because we need to visit each node in the tree exactly once to swap its left and right child nodes.
Auxiliary Space: O(h), where h is the height of the binary tree. This is because the maximum amount of space used by the algorithm at any given time is the size of the call stack, which is at most equal to the height of the binary tree. This is because each recursive call to mirror adds a new frame to the call stack, and the stack grows to a maximum depth of the height of the tree. Therefore, the space used by the algorithm is proportional to the height of the tree.
Approach 2:
In order to change the original tree in its mirror tree, then we simply swap the left and right link of each node. If the node is leaf node then do nothing.
C++
#include <iostream>using namespace std;typedef struct treenode { int val; struct treenode* left; struct treenode* right;} node;// Helper function that // allocates a new node with the// given data and NULL left and right pointersnode* createNode(int val){ node* newNode = (node*)malloc(sizeof(node)); newNode->val = val; newNode->left = NULL; newNode->right = NULL; return newNode;}// Function to print the inrder traversalvoid inorder(node* root){ if (root == NULL) return; inorder(root->left); printf("%d ", root->val); inorder(root->right);}// Function to convert to mirror treetreenode* mirrorTree(node* root){ // Base Case if (root == NULL) return root; node* t = root->left; root->left = root->right; root->right = t; if (root->left) mirrorTree(root->left); if (root->right) mirrorTree(root->right); return root;}// Driver Codeint main(){ node* tree = createNode(5); tree->left = createNode(3); tree->right = createNode(6); tree->left->left = createNode(2); tree->left->right = createNode(4); printf("Inorder of original tree: "); inorder(tree); // Function call mirrorTree(tree); printf("\nInorder of Mirror tree: "); inorder(tree); return 0;} |
Java
import java.util.*;class GFG{ static class Node { int val; Node left; Node right;}// Helper function that allocates// a new node with the given data// and null left and right referencespublic static Node createNode(int val){ Node newNode = new Node(); newNode.val = val; newNode.left = null; newNode.right = null; return newNode;}// Function to print the inorder traversalpublic static void inOrder(Node root){ if (root == null) return; inOrder(root.left); System.out.print(root.val + " "); inOrder(root.right);}// Function to convert to mirror tree// by swapping the left and right links.public static Node mirrorTree(Node root){ if (root == null) return null; Node left = mirrorTree(root.left); Node right = mirrorTree(root.right); root.left = right; root.right = left; return root;}// Driver Codepublic static void main(String args[]){ Node tree = createNode(5); tree.left = createNode(3); tree.right = createNode(6); tree.left.left = createNode(2); tree.left.right = createNode(4); System.out.print("Inorder of original tree: "); inOrder(tree); // Function call mirrorTree(tree); System.out.print("\nInorder of mirror tree: "); inOrder(tree);}}// This code is contributed by Ryan Ranaut |
Python3
# codeclass Node: def __init__(self,data): self.left = None self.right = None self.data = datadef inOrder(root): if root is not None: inOrder(root.left) print (root.data, end = ' ') inOrder(root.right)#we recursively call the mirror function which swaps the right subtree with the left subtree.def mirror(root): if root is None: return mirror(root.left) mirror(root.right) root.left, root.right = root.right, root.leftroot = Node(1)root.left = Node(2)root.right = Node(3)root.left.left = Node(4)root.right.left = Node(5)print("The inorder traversal of the tree before mirroring:",end=' ')print(inOrder(root))# 4 2 1 5 3print()mirror(root)print("The inorder traversal of the tree after mirroring:",end=' ')print(inOrder(root))# 3 5 1 2 4 |
C#
using System;public class GFG{ public class Node { public int val; public Node left; public Node right;}// Helper function that allocates// a new node with the given data// and null left and right referencespublic static Node createNode(int val){ Node newNode = new Node(); newNode.val = val; newNode.left = null; newNode.right = null; return newNode;}// Function to print the inorder traversalpublic static void inOrder(Node root){ if (root == null) return; inOrder(root.left); Console.Write(root.val + " "); inOrder(root.right);}// Function to convert to mirror tree// by swapping the left and right links.public static Node mirrorTree(Node root){ if (root == null) return null; Node left = mirrorTree(root.left); Node right = mirrorTree(root.right); root.left = right; root.right = left; return root;}// Driver Codepublic static void Main(String []args){ Node tree = createNode(5); tree.left = createNode(3); tree.right = createNode(6); tree.left.left = createNode(2); tree.left.right = createNode(4); Console.Write("Inorder of original tree: "); inOrder(tree); // Function call mirrorTree(tree); Console.Write("\nInorder of mirror tree: "); inOrder(tree);}}// This code is contributed by shivanisinghss2110 |
Javascript
<script> class Node { constructor() { this.val=0; this.left=this.right=null; }}// Helper function that allocates// a new node with the given data// and null left and right referencesfunction createNode(val){ let newNode = new Node(); newNode.val = val; newNode.left = null; newNode.right = null; return newNode;}// Function to print the inorder traversalfunction inOrder(root){ if (root == null) return; inOrder(root.left); document.write(root.val + " "); inOrder(root.right);}// Function to convert to mirror tree// by swapping the left and right links.function mirrorTree(root){ if (root == null) return null; let left = mirrorTree(root.left); let right = mirrorTree(root.right); root.left = right; root.right = left; return root;}// Driver Code let tree = createNode(5); tree.left = createNode(3); tree.right = createNode(6); tree.left.left = createNode(2); tree.left.right = createNode(4); document.write("Inorder of original tree: " ); inOrder(tree); // Function call mirrorTree(tree); document.write("<br>" +"\nInorder of mirror tree: "); inOrder(tree);// This code is contributed by shivanisinghss2110</script> |
Output
Inorder of original tree: 2 3 4 5 6 Inorder of Mirror tree: 6 5 4 3 2
Time complexity: O(N) where N is the number of nodes in given binary tree.
Auxiliary Space: O(h) where h is the height of the tree. due to recursion call stack.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
