About usWhy usInstructorsReviewsCostFAQContactBlogRegister for Webinar

Mirror Image of Binary Tree Problem

You are given the root node of a binary tree T. You need to modify that tree in place, transform it into the mirror image of the initial tree T.

Example

Input:


        0

      /    \

    1     2

   /  \    /   \

 3    4 5    6


Output:


        0

      /    \

    2     1

   /  \    /   \

 6    5 4    3


As we can easily visualise that input binary tree and output binary tree are mirror images of each other. So if A and B are two binary trees which are mirror images of each other then taking a mirror image of A would generate B and vice versa.

Notes

Input Parameters: The function has one parameter of type TreeNode: the root node of binary tree T.

Solutions

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

1) optimal_solution1.java

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) where n is the number of tree nodes.

Auxiliary Space Used:

O(n) where n is the number of tree nodes. 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).


2) optimal_solution2.java

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:

1. Get next node from the queue

2. Swap its left and right child nodes

3. Push its left and right children into the queue

Time Complexity:

O(n) where n is the number of nodes.

Auxiliary Space Used:

O(n) where n is the number of nodes.

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) where n is the number of nodes.

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).


// -------- START --------
    public static void mirror_image(TreeNode root) {
        if (root == null)
            return;
        
        Queue queue = new LinkedList();
        queue.add(root);
        // Do BFS. While doing BFS, keep swapping
        // left and right children
        while(!queue.isEmpty()) { 
            // pop top node from queue 
            TreeNode cur_node = queue.poll();
            
            // swap left child with right child
            TreeNode 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); 
        } 
    } 
    // -------- END --------


Attend our Free Webinar on How to Nail Your Next Technical Interview

Recommended Posts

All Posts