Do you want to know how to convert Binary Tree To Mirror Tree? In this article, you will learn to convert a Binary Tree to Its Mirror or Inverted view.
What is Mirror Tree?
When you are having a given binary tree, then the mirror of that tree would be that all the left children of the root node should be right children in the mirror tree, and similarly, all the right children of the root node should be left children of the mirror tree.
In the below code we will see how you can implement the code to mirror the binary tree. We are going to use the recursive method to swap the left and right child using postorder traversal or preorder traversal.
C++ Implementation of Mirror Tree
Below code is the implementation of Conversion of Mirror or Inverted Binary Tree in C++.
#include<bits/stdc++.h> using namespace std; /** * Definition for a binary tree node. */ struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode() : val(0), left(nullptr), right(nullptr) {} TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} }; class MirrorTree { public: //Function to Convert the Binary Tree to Inverted or Mirror Tree // And Return the Root Node. TreeNode* invertTree(TreeNode* root) { //If Root is NULL then return NULL if(!root) return NULL; TreeNode* leftNode = invertTree(root->left); TreeNode* rightNode = invertTree(root->right); root->left = rightNode; root->right = leftNode; return root; } //Function to Print the Inorder Traversal of Tree void printInorder(TreeNode* root){ if(!root) return; printInorder(root->left); cout<<root->val<<" "; printInorder(root->right); } }; int main(){ //Initialization MirrorTree objToCallFunc; //Creating Example Tree Structure to Mirror it // Or Create A Inverted Tree out of it. TreeNode* root = new TreeNode(4); root->left = new TreeNode(2); root->right = new TreeNode(6); root->left->left = new TreeNode(1); root->left->right = new TreeNode(3); root->right->left = new TreeNode(5); root->right->right = new TreeNode(7); //Print the Original Tree. cout<<"Origin Binary Tree: "; objToCallFunc.printInorder(root); cout<<endl; //creating the MirrorTree Object to call the function // To create the inverted Image. TreeNode* invertedTree = objToCallFunc.invertTree(root); //Print the Inorder Traversal of inverted Tree. cout<<"Mirror Binary Tree: "; objToCallFunc.printInorder(invertedTree); return 0; }
Output:
Origin Binary Tree: 1 2 3 4 5 6 7
Mirror Binary Tree: 7 6 5 4 3 2 1
As you can see in the above output, in the first Inorder traversal[1] the number is printed in ascending order, and when we flipped the tree all the values are printed in descending order.
Python Implementation of Mirror or Inverted Tree
Below is the Python implementation for the above problem.
# Definition for a binary tree node. from os import sep class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def invertTree(root: TreeNode): if root == None: return None leftNode = invertTree(root.left) rightNode = invertTree(root.right) root.right = leftNode root.left = rightNode return root def inorderTraversal(root: TreeNode): if root==None: return inorderTraversal(root.left) print(root.val, end=" ") inorderTraversal(root.right) #Creating the Tree root = TreeNode(4) root.left = TreeNode(2) root.right = TreeNode(6) root.left.left = TreeNode(1) root.left.right = TreeNode(3) root.right.left = TreeNode(5) root.right.right = TreeNode(7) #calling inorder Traversal to Print the Tree inorderTraversal(root) newRoot = invertTree(root) print("\nNew Mirror Tree") inorderTraversal(newRoot) print(newRoot)
Output:
1 2 3 4 5 6 7
New Mirror Tree
7 6 5 4 3 2 1
That is all for how to convert Binary Tree to Mirror Tree or Inverted Tree. Let me know if you have any questions in the comment section. Also, let me know if you want the code in a different language as well.
And please follow us on Facebook and Twitter. Let us know the questions and answer you want to cover in this blog.
Further Read: