How to Convert Binary Tree to Mirror Tree (Inverted)

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.

How to Convert Binary Tree to Mirror Tree (Inverted)
Given Binary Tree
How to Convert Binary Tree to Mirror Tree (Inverted)
Inverted or Mirror Binary Tree

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 the 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:

  1. Kadane’s Algorithm: Maximum Sum Subarray Problem
Share your love

One comment

Leave a Reply