Convert a Binary Tree to Its Mirror Tree

A binary tree is an important data structure. It has numerous applications in programming. A binary tree is a type of the tree data structure in which each node has two child nodes. In this tutorial, we will learn how to convert a binary tree to its mirror tree in C++, Java, and Python.

Problem Statement

Given a binary tree, you need to convert it into its mirror tree. This problem is also known as inverting a binary tree problem.

Example

Approach

We can use DFS to solve this problem. Consider a case when you need to convert the following binary tree into its mirror tree:

      1
   /     \
  2       3

We would simply swap the left and right children of the root. This algorithm can be extended on subtrees as well. We traverse a tree in any order and keep swapping left and right children for each node. Ultimately, this would result in the mirror image of the given tree. Most tree problems are solved by extending the algorithm as we did here.

Complexity Analysis

The time complexity would be O(N), and the space complexity would also be O(N) in the worst case.

How to Convert a Binary Tree to Its Mirror Tree?

Here, we will invert a binary tree in three different programming languages, namely C++, Java, and Python.

1. C++ Programming

#include <iostream>
using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left, *right;

    TreeNode(int val)
    {
        this->val = val;
        this->left = this->right = nullptr;
    }
};

void printTree(TreeNode* root)
{
    if (root == nullptr) {
        return;
    }

    cout << root->val << " ";
    printTree(root->left);
    printTree(root->right);
}

bool dfs(TreeNode* root)
{
    if (!root) {
        return true;
    }

    // convert left subtree
    dfs(root->left);

    // convert right subtree
    dfs(root->right);

    // swap left subtree with right subtree
    swap(root->left, root->right);
}

int main()
{
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);

    dfs(root);

    printTree(root);

    return 0;
}

Output

1 3 2

2. Java Programming

class TreeNode
{
    int val;
    TreeNode left = null, right = null;

    TreeNode(int val) {
        this.val = val;
    }
}

class Main
{
    public static void printTree(TreeNode root)
    {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        printTree(root.left);
        printTree(root.right);
    }

    public static void swap(TreeNode root)
    {
        if (root == null) {
            return;
        }
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }

    public static void dfs(TreeNode root)
    {
        if (root == null) {
            return;
        }

        // convert left subtree
        dfs(root.left);

        // convert right subtree
        dfs(root.right);

        // swap left subtree with right subtree
        swap(root);
    }

    public static void main(String[] args)
    {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3); 

        dfs(root);

        printTree(root);
    }
}

Output

1 3 2

3. Python Programming

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
def printTree(root):
    if root is None:
        return

    print(root.val, end=' ')
    printTree(root.left)
    printTree(root.right)

def swap(root):
    if root is None:
        return

    temp = root.left
    root.left = root.right
    root.right = temp

def dfs(root):
    if root is None:
        return

    # convert left subtree
    dfs(root.left)

    # convert right subtree
    dfs(root.right)

    # swap left subtree with right subtree
    swap(root)

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
dfs(root)
printTree(root)

Output

1 3 2

Conclusion

That sums up this tutorial on inverting a binary tree. We used the depth-first search for implementing the logic of converting a binary tree to its mirror tree.

People are also reading:

• Subarray with Sum k
• Find Maximum Length Subarray Having an Equal Number of 0’s and 1’s
• Merge Two Sorted Arrays in-place
• Find Maximum Subarray Sum
• Rod Cutting Problem – Dynamic Programming
• Sort binary array in linear time
• Maximum of all Subarrays of size K
• Minimum Edit Distance
• The Stock Span Problem
• Find maximum of minimum for every window size in a given array