Binary Tree Upside Down — Re-root the Left Spine in O(n)

Problem Statement#

Given the root of a binary tree where every right node has either a sibling left node and is a leaf, or no nodes at all, flip the tree upside down so that the original left child becomes the new root, the original root becomes its right child, and the original right child becomes its left child.

Constraints:

• 0 <= number of nodes <= 10
• 1 <= Node.val <= 10
• Every right node has a sibling left node and is a leaf, or no children at all

Input:  root = [1,2,3,4,5]
        1
       / \
      2   3
     / \
    4   5
Output: [4,5,2,null,null,3,1]
        4
       / \
      5   2
         / \
        3   1

Input:  root = []
Output: []

Why This Problem Matters#

LeetCode 156 "Binary Tree Upside Down" is a classic Google interview question and also pops up at LinkedIn and Bloomberg. It tests pointer manipulation discipline — the same skill needed for reversing a linked list, but in a tree shape. Many candidates panic at the rewiring; calm, ordered pointer surgery is exactly what interviewers want to see.

It is also a great problem to demonstrate both recursive and iterative thinking. The recursive version reads like the problem statement; the iterative version proves you can save the recursion stack for O(1) extra space.

The Core Insight#

Because right nodes are always leaves with a sibling, the tree is essentially a left spine with optional right-leaf siblings at each level. Walk down the left spine. At each node, the new root is the bottom-left node. As you unwind, take the current node, set its new left child to the original right sibling, and set its new right child to the original parent — exactly like reversing a linked list with one extra pointer.

The iterative version uses four pointers: curr, prev, next, and temp (saved right child). At each step, snapshot the right child and the left child, then rewire.

Visual Dry Run#

Input [1,2,3,4,5]. Walk left from 1 to 4.

After loop, prev points to 4, the new root.

Solution (Optimal)#

class Solution:
    def upsideDownBinaryTree(self, root):
        curr, prev, next_node, temp = root, None, None, None
        while curr:
            next_node = curr.left
            curr.left = temp
            temp = curr.right
            curr.right = prev
            prev = curr
            curr = next_node
        return prev

var upsideDownBinaryTree = function(root) {
    let curr = root, prev = null, next = null, temp = null;
    while (curr) {
        next = curr.left;
        curr.left = temp;
        temp = curr.right;
        curr.right = prev;
        prev = curr;
        curr = next;
    }
    return prev;
};

Time: O(n) — visit every node on the left spine exactly once. Space: O(1) — only four pointers; recursion stack avoided.

Common Mistakes#

• Updating curr.left and curr.right in the wrong order, clobbering temp before saving it.
• Returning curr (which is null at end) instead of prev.
• Trying a generic recursive flip without using the leaf invariant — leads to a wrong answer when right is not a leaf.
• Forgetting the empty-tree base case: return null when root is null.
• Confusing the iterative flow with linked-list reversal — there are two extra pointers (temp, next) here.

Interview Tips#

• Sketch the rewiring on paper before coding. Pointer order matters.
• State the invariant: every right node is a leaf with a left sibling.
• Offer the recursive version first ("recurse on left, then rewire"), then the iterative O(1)-space upgrade.
• Mention this is a special case of "re-root a tree" — generic re-rooting is a richer technique.

Follow-up Questions#

• Recursive version: write it and explain the post-order rewiring. Hint: recurse on root.left, then set root.left.left = root.right and root.left.right = root.
• Re-root at arbitrary node: generalize to any node, not just the leftmost leaf. Hint: parent pointers or DFS path stack.
• Reverse the operation: given the upside-down tree, reconstruct the original. Hint: invert the pointer rewiring.
• N-ary version: extend the idea to a tree where the spine can have multiple children. Hint: pick a fixed traversal order.
• Validate input: check the right-leaf-with-left-sibling invariant before flipping. Hint: DFS validator.

Key Takeaways#

• LeetCode 156 reduces to walking a left spine and rewiring three pointers per node.
• The right-leaf-with-left-sibling invariant is what makes a clean rewiring possible.
• Iterative solution achieves O(1) extra space — better than recursion's O(h) stack.
• Save the original right child in temp before overwriting it, mirroring linked-list reversal.
• New root is the original leftmost leaf.
• Frequently appears in Google, LinkedIn, and Bloomberg phone screens.
• A good warm-up before harder pointer-rewiring problems like Flatten Binary Tree to Linked List.