Invert Binary Tree

Inverting a Binary Tree is a problem asked in a lot of interviews and we will be tackling it in a simple but efficient manner. Any tree-related problem should be attempted to be solved in a recursive approach since Tree is a localized data structure i.e small trees make up large trees. 

Example:

Input:
 
     4
   /   \
  2     7
 / \   / \
1   3 6   9

Output:

     4
   /   \
  7     2
 / \   / \
9   6 3   1

We have used the following TreeNode.java to implement the solution.

public class TreeNode {

    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int x) {
        this.val = x;
        this.left = null;
        this.right = null;
    }
}

Recursive Implementation:

The inverse of an empty tree is the empty tree. The inverse of a tree with root r, and subtrees right and left, is a tree with root r, whose right subtree is the inverse of left, and whose left subtree is the inverse of right.

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null){
            return root;
        }
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}

Since each node in the tree is visited only once, the time complexity is O(n), where n is the number of nodes in the tree. We cannot do better than that since at the very least we have to visit each node to invert it. Because of recursion, O(h) function calls will be placed on the stack in the worst case, where h is the height of the tree. Because of h∈O(n), the space complexity is O(n).

Iterative Implementation:

The idea is that we need to swap the left and right child of all nodes in the tree. So we create a queue to store nodes whose left and right children have not been swapped yet. Initially, only the root is in the queue. As long as the queue is not empty, remove the next node from the queue, swap its children, and add the children to the queue. Null nodes are not added to the queue. Eventually, the queue will be empty and all the children swapped, and we return the original root.

class Solution {
    public TreeNode iterativeInvert(TreeNode root) {
        if (root == null) {
            return null;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode current = queue.poll();
            TreeNode tempNode = current.left;
            current.left = current.right;
            current.right = tempNode;
            if (current.left != null) {
                queue.add(current.left);
            }
            if (current.right != null) {
                queue.add(current.right);
            }
        }
        return root;
    }
}

Categories: Binary Tree

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s