Convert a Binary Tree to Its Mirror Tree

Posted in /   /  

Convert a Binary Tree to Its Mirror Tree

Ramya Shankar
Last updated on June 10, 2022

    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:

    Leave a Comment on this Post

    0 Comments