Coding Interview: Binary Tree Upside Down

While preparing for my interviews I came across a very interesting tree problem. The problem goes like - given a binary tree, we need to turn the tree upside down so that the deepest and left most node becomes the root of the tree. The rules of making the tree upside down is as follow:

1. The original left child becomes the new root.
2. The original root becomes the new right child.
3. The original right child becomes the new left child.
4. It is guaranteed that every node in the tree has either 0 or 2 child.

Ok, let’s first try to understand what the question is asking us to do. First thing we need to understand is we need at least 3 nodes to turn the tree. We can’t rotate the tree with just 2 nodes.

Invalid case. Can’t turn tree.

Now let’s look at how we will rotate the tree with 3 nodes :

The leftmost node is now root and left child of new root is now right child of old root.

We can quickly observe few salient characteristics:

1. The leftmost child become “new root”.
2. The “old root” is now the right child of “new root”
3. The left child of “new root” is the right child of “old root”

By this point, we can almost sense that there is a pattern to how the upside down rotation will happen. To make things more clear, let’s take a relatively bigger tree and observe how rotation will happen.

Example: Complete Binary Tree with Depth 2

We should be able to draw more conclusion looking the above example:

1. The link between a node and its right child generally break.
2. The right child of left node = parent.
3. However, if their are children of right node, then they remain intact. Observe the purple node.

Algorithm: We first have to find the new node which is the leftmost node of the entire tree. Next we need to build the new tree layer by layer from bottom to up. While building our tree from bottom to up, we will make use the observations we gathered from previous examples. Let’s look at one example of what we may want to do. The red arrows depicts the older state and green depicts the changes we want to make. The node where we are at is called “curr”.

Modifying the links at a given node

The changes boils down to:

curr.left.left = curr.right;
curr.left.right = curr;
curr.left = null;
curr.right = null;

Now all that is left is we perform the above operation recursively.

Code:

class Solution {
    public TreeNode upsideDownBinaryTree(TreeNode root) {
        if(root == null) {
            return root;
        }
        return rotate(root);
    }
    
    public TreeNode rotate(TreeNode curr) {
        if(curr.left == null) {
            return curr;
        }
        TreeNode node = rotate(curr.left);
        curr.left.left = curr.right;
        curr.left.right = curr;
        curr.left = null;
        curr.right = null;
        return node;
    }
}

Time Complexity: If we consider a balance binary tree the time complexity for doing an upside down rotation will be O(log(N)) where N is the number of nodes in the tree.