About usWhy usInstructorsReviewsCostFAQContactBlogRegister for Webinar
Our June 2021 cohorts are filling up quickly. Join our free webinar to Uplevel your career

Mirror Image Of Binary Tree Problem

Coding problems on trees are asked frequently at tech interviews. Creating a mirror tree from the given binary tree is one such popular DSA problem. Let's look at what the problem entails and how to solve it.

Mirror Image Of Binary Tree Problem Statement

Given the root of a binary tree, transform the tree in-place into its mirror image.

Example

        0
      /   \
    1       2
   /  \   /   \
  3    4  5    6

Output:

         0
      /    \
    2        1
   /  \    /   \
  6    5   4    3

Notes

  • The function doesn't need to return anything. Modify the tree in-place.

Constraints:

  • 1 <= number of nodes <= 100000
  • 0 <= node value < number of nodes
  • Node values are unique

We provided two solutions: a recursive one and an iterative one.

We will refer to the total number of nodes in the given tree as n.

Mirror Image Of Binary Tree Solution 1: Depth First Search

This is a recursive solution. The main task is to swap left and right children for every node of the tree. We are calling the function recursively and making sure that leaf nodes are handled first then their parents and it goes up to the root node.

Time Complexity

O(n).

Auxiliary Space Used

O(n).

That extra space is used for the call stack.

Space Complexity

O(n).

Input is O(n) because we are storing n nodes relationships and each relationship occupies O(1) space and auxiliary space used is O(n). So, O(n) + O(n) = O(n).

Code For Mirror Image Of Binary Tree Solution 1: Depth First Search

    /*
    * Asymptotic complexity in terms of number of nodes \`n\` in the given tree:
    * Time: O(n).
    * Auxiliary space: O(n).
    * Total space: O(n).
    */

    public static void mirror_image(BinaryTreeNode root) {
        root = mirror_image_util(root);
    }

    public static BinaryTreeNode mirror_image_util(BinaryTreeNode root){
        if (root == null)
            return root;

        BinaryTreeNode left = mirror_image_util(root.left);
        BinaryTreeNode right = mirror_image_util(root.right);

        // Swap the left and right pointers.
        root.left = right;
        root.right = left;
        return root;
    }

Mirror Image Of Binary Tree Solution 2: Breadth First Search

This solution traverses the tree breadth first using a loop and a queue, without making use of recursion. We initialize the queue with the root node. Then we do the following until the queue is empty:

  • Get next node from the queue
  • Swap its left and right child nodes
  • Push its left and right children into the queue

Time Complexity

O(n).

Auxiliary Space Used

O(n).

We are using a queue for storing nodes to do BFS traversal over the tree. In the worst case scenario, queue size will be n.

Space Complexity

O(n).

Input is O(n) because we are storing n nodes relationships and each relationship occupies O(1) space and auxiliary space used is O(n). So, O(n) + O(n) = O(n).

Code For Mirror Image Of Binary Tree Solution 2: Breadth First Search

    /*
    * Asymptotic complexity in terms of number of nodes \`n\` in the given tree:
    * Time: O(n).
    * Auxiliary space: O(n).
    * Total space: O(n).
    */

    public static void mirror_image(BinaryTreeNode root) {
        if (root == null)
            return;

        Queue<BinaryTreeNode> queue = new LinkedList<BinaryTreeNode>();
        queue.add(root);
        // Do BFS. While doing BFS, keep swapping
        // left and right children
        while(!queue.isEmpty()) {
            // Pop top node from queue.
            BinaryTreeNode cur_node = queue.poll();

            // Swap left child with right child.
            BinaryTreeNode temp = cur_node.left;
            cur_node.left = cur_node.right;
            cur_node.right = temp;

            // Push left and right children.
            if (cur_node.left != null)
                queue.add(cur_node.left);
            if (cur_node.right != null)
                queue.add(cur_node.right);
        }
    }

We hope that these solutions to creating a mirror image of a binary tree have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart’s FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 17 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

‍To learn more, register for the FREE webinar.

Try yourself in the Editor

Note: Input and Output will already be taken care of.

Recommended Posts

All Posts