LeetCode 156 – Binary Tree Upside Down

Binary Tree Upside Down is pure pointer surgery on a tree whose shape is guaranteed to be convenient. There is no search, no accumulator and no complexity to argue about — the entire problem is doing four assignments in an order that does not destroy what the next one needs, which is a skill worth practising on something this small.

The problem

Given a binary tree where every right child is a leaf and has a sibling — so the tree leans left — turn it upside down: the leftmost node becomes the new root, each original left child becomes a parent, and the original parent becomes its right child while the original right child becomes its left child.

      1                     4
     / \                   / \
    2   3       ->        5   2
   / \                       / \
  4   5                     3   1

[1]      -> [1]        nothing to turn
[]       -> []
[1,2,3]  -> 2 with left 3 and right 1

The transformation, stated per node: root.left becomes the parent, root.right becomes that parent's left child, and root becomes its right child.

     root                  root.left
     /  \        ->         /     \
 left   right          right      root

The guaranteed shape is what makes this tractable. Because every right child is a leaf, the "spine" of left children is the only path that recurses, and the right children just get relocated without further work.

The recursion

Walk down the left spine to the bottom — that node is the new root and never moves. Then, coming back up, rewire each node into its former left child.

newRoot = recurse(root.left)        go all the way down first

root.left.left  = root.right        the old right child hangs left
root.left.right = root              the old parent hangs right
root.left  = null                   root is now a leaf...
root.right = null                   ...so both its pointers must go

return newRoot                      unchanged all the way back up

The base case is root == null || root.left == null: no left child means this is the bottom of the spine, and it is the new root.

The order is the problem

All four assignments reference root.left or root.right, and two of them overwrite exactly those fields. Null out root.left before using it and the whole subtree is lost:

root.left = null;              <- WRONG if done first
root.left.left = root.right;   <- NullPointerException

Read the fields before you write them. It is the same rule that governs Flatten Binary Tree and Merge Sorted Array: when a write would clobber something unread, either reorder the writes or save the value first. Here reordering is enough.

Java

class Solution {
    public TreeNode upsideDownBinaryTree(TreeNode root) {
        // No left child means we are at the bottom of the spine: the new root.
        if (root == null || root.left == null) return root;

        TreeNode newRoot = upsideDownBinaryTree(root.left);

        // READ root.left and root.right before overwriting either.
        root.left.left = root.right;    // old right child becomes the left child
        root.left.right = root;         // old parent becomes the right child

        root.left = null;               // root is now a leaf
        root.right = null;

        return newRoot;                 // unchanged all the way back up
    }
}

newRoot is threaded straight through every level untouched. The recursion is not computing anything on the way back up — it is just providing the traversal order, and the return value is a constant once the bottom is reached.

Both root.left and root.right must be nulled. Forgetting root.right leaves the old right child reachable from two places, which produces a structure that prints correctly for a few levels and is not a tree.

Python

class Solution:
    def upsideDownBinaryTree(self, root: TreeNode) -> TreeNode:
        if root is None or root.left is None:
            return root

        new_root = self.upsideDownBinaryTree(root.left)

        root.left.left = root.right       # read before writing
        root.left.right = root

        root.left = None
        root.right = None

        return new_root

The iterative version

The recursion is O(h) stack, and on this tree shape h is the length of the left spine — potentially the whole tree. Walking down and rewiring as you go removes it, at the cost of carrying three references:

    def upsideDownIterative(self, root: TreeNode) -> TreeNode:
        current, parent, parent_right = root, None, None

        while current:
            next_node = current.left       # save before overwriting

            current.left = parent_right    # what was the parent's right child
            parent_right = current.right   # remember ours for the next iteration
            current.right = parent         # the parent hangs to our right

            parent = current
            current = next_node

        return parent                      # the last node visited is the new root

Five assignments in a fixed order, each reading a value the next one is about to destroy. Write out one iteration by hand before trusting it — this is the kind of code that is easy to nod along with and hard to reproduce.

O(1) space, and it returns parent rather than current because the loop exits one step past the end.

Complexity

	Time	Space
Recursive	`O(n)`	`O(h)` stack
Iterative	`O(n)`	`O(1)`

Every node on the left spine is visited once; right children are relocated in constant time without being descended into, because the problem guarantees they are leaves. That guarantee is doing real work — without it this would be a much harder problem, and saying so shows you read the constraints rather than skimming them.

What the interviewer is checking

That you read root.left and root.right before nulling them.
That both pointers are nulled, so the old root becomes a genuine leaf.
The base case: no left child means this is the new root.
That the new root is threaded back unchanged, not recomputed.
Empty tree and single node.
That the guaranteed shape is what makes right children free to relocate.
Bonus: the O(1) iterative version, written carefully.