p11 Invert Binary Tree — Progressive Hints

Rule: Read ONE hint. Set a 5-minute timer. Try again. Only read the next hint if the timer expires.

Hint 1 — Pattern family

This is a tree-mutation problem. The structure of every tree-recursion is:

  1. Base case (what to do at a null subtree)
  2. Recurse on left and right subtrees
  3. Combine / mutate at the current node

Ask yourself: what does this function return for a subtree?

Hint 2 — The contract

Your function takes a subtree root, mutates it so the entire subtree is inverted, and returns the (same, now-inverted) root. Base case for null: return null.

Hint 3 — Key insight

To invert a tree at node N:

  1. Invert N’s left subtree (recursively).
  2. Invert N’s right subtree (recursively).
  3. Swap N’s left and right child pointers.

Steps 1 and 2 are independent. Step 3 can happen before OR after them — both orders give the same result because the swap operates on pointers while the recursion operates on subtrees.

Hint 4 — Pseudocode (recursive) + iterative skeleton

Recursive:

def invert(node):
    if node is None: return None
    node.left, node.right = invert(node.right), invert(node.left)
    return node

Iterative BFS:

if root is None: return None
queue = deque([root])
while queue:
    cur = queue.popleft()
    swap cur.left and cur.right
    if cur.left: queue.append(cur.left)
    if cur.right: queue.append(cur.right)
return root

Hint 5 — Full algorithm + production notes

Recursive — 4 lines:

def invert(node):
    if node is None:
        return None
    node.left, node.right = invert(node.right), invert(node.left)
    return node

The tuple-swap on the right evaluates BOTH recursive calls first, then atomically assigns to node.left and node.right. No temporary needed.

Time O(N) — visit every node once. Space O(H) — recursion depth equals tree height. For balanced trees O(log N); for skewed, O(N).

Production note — recursion limit: Python’s default recursion limit is 1000. A tree of depth >1000 (skewed) will raise RecursionError. Two fixes: sys.setrecursionlimit(10_000) (bumps the limit) or rewrite iteratively (heap-allocated, no overflow). Always offer the iterative version when the interviewer asks about scale.

Non-mutating variant (when the input can’t be touched):

def invert_pure(node):
    if node is None: return None
    return TreeNode(node.val, invert_pure(node.right), invert_pure(node.left))

Same O(N) time, same O(H) depth, plus O(N) for new nodes. Required for thread-safe / persistent / read-only trees.

Involution property (great for property-based testing): invert(invert(x)) == x for any tree x. The stress_test exploits this.