Convert a Binary Tree to Its Mirror Tree

By | October 25, 2021

Problem 

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

Example 

Vamware

Approach

We can use DFS to solve this problem. Consider a case when you need to convert the following binary tree into the 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 of the 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.

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

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

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

People are also reading:

Leave a Reply

Your email address will not be published. Required fields are marked *