p11 — Invert Binary Tree

Source: LeetCode 226 · Easy · Topics: Tree, DFS, BFS, Binary Tree Companies (2024–2025 frequency): Google (very high), Amazon (high), Microsoft (high), Meta (medium), Apple (medium), Bloomberg (medium) Loop position: phone screen warmup; the legendary “Max Howell / Homebrew” tweet question (Google rejected him for not solving it). Almost universally asked.

1. Quick Context

This is the canonical “I expect you to know how to recurse on a tree” question. The recursive solution is 4 lines. The interviewer is testing whether recursion on a tree is reflex for you. Mid candidates get it but stumble on the base case. Senior candidates write it cold, then immediately offer the iterative BFS variant when asked. Staff candidates discuss in-place vs out-of-place, mutation contract, and the wider mirror-walk family (LC 100, 101, 951).

The “trick” is recognizing the pattern: what does this function return for a subtree? Answer: the inverted subtree’s root. Base case: empty subtree returns empty. Recursive case: swap the children (after recursively inverting them).

What it looks like it tests: can you recurse on a tree? What it actually tests: is recursion reflex, can you pivot to iterative under pressure, do you state the base case before coding?

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/invert-binary-tree/

STOP. Set a 5-minute timer. Code it cold — BOTH recursive AND iterative. Do not read past this section until both solved or expired.

If you’ve seen it: target 3 min for recursive, 4 min for iterative. Articulate base case aloud first.

3. Prerequisite Concepts

• TreeNode definition and binary tree mental model (phase-01 §9)
• Recursion stack & base case discipline (phase-01 §8)
• BFS with collections.deque for iterative tree traversal
• DFS with explicit stack for iterative tree traversal
• Python’s sys.setrecursionlimit and when to bump it
• In-place mutation vs. building a new tree (interview contract)

4. How to Approach (FRAMEWORK Steps 1–9 applied)

Step 1 — Restate: “Given the root of a binary tree, swap every node’s left and right children. Return the modified root.”

Step 2 — Clarify:

• “May I mutate the input?” (Usually yes per LC. If not, build a new tree — different algorithm.)
• “What’s the tree’s maximum depth?” (LC says up to 100. Production: ask. >1000 risks Python recursion overflow.)
• “Empty tree input?” (Yes — return None.)
• “Does the tree have unique values?” (Irrelevant — we operate on structure, not values.)
• “Is this a BST?” (No — inverting destroys BST property; the problem cares about structural mirror, not ordering.)

Step 3 — Constraints: N up to 100 per LC; trivial. Production: could be millions. Time O(N) — must touch every node. Space O(H) for recursion (H = height; O(log N) balanced, O(N) skewed).

Step 4 — Examples:

• [4,2,7,1,3,6,9] → [4,7,2,9,6,3,1] (canonical LC).
• [] → [] (empty).
• [1] → [1] (single node — swap does nothing).
• [1,2] → [1,null,2] (left-only becomes right-only).
• Skewed left-only of depth 100: tests recursion-stack handling.

Step 5 — Brute Force: Recursion IS the natural form here. No “brute force” with worse complexity — every approach touches every node once at O(N).

Step 6 — Complexity: O(N) time (must visit each node). Space O(H) recursive call stack OR O(W) for iterative BFS (W = max width). For balanced trees O(log N); skewed O(N) either way.

Step 7 — Pattern Recognition: “Mutate every node in a tree” → post-order or pre-order DFS (either works; we choose pre-order: swap, then recurse). Iterative variant: BFS queue OR DFS stack. This is the prototypical tree-mutation algorithm.

Step 8 — Optimize: No further optimization possible — already optimal. The “optimization” is recognizing the iterative variant matters for production code where recursion stack overflow is a real risk for trees of depth >1000.

Step 9 — Prove correctness: Induction on tree size. Base case: empty tree is its own mirror (vacuously inverted). Inductive step: assume invert correctly inverts trees of size < N. For tree of size N: recursively invert left and right subtrees (both have size < N, so correct by hypothesis). Swap them. Result: original-left (now inverted) is at right; original-right (now inverted) is at left. By definition, this IS the inverted tree.

5. Progressive Hints

If stuck for 5 minutes, open hints.md. One hint, 5-min timer, retry.

6. Deeper Insight — Why It Works

The “return the mutated subtree root” framing: every tree-mutation recursion should be written by first answering “what does this function return for a subtree?” Here: it returns the root of the now-inverted subtree (which happens to be the same node we received, just with mutated children). Stating this aloud before coding is the difference between Senior and Mid signal. Mid candidates start typing; Senior candidates state the contract.

Why pre-order vs post-order doesn’t matter for THIS problem: swap-then-recurse and recurse-then-swap both work because the swap operates on the children pointers, and the recursion operates on the subtrees. The two are commutative for this specific operation. (In other problems — e.g., serializing while mutating — order matters; train yourself to ask “does my operation commute with the recursion?”)

In-place vs new-tree contract: LC’s signature returns the (same) root, signaling mutation is fine. Production may forbid mutation. The non-mutating version: return TreeNode(node.val, invert(node.right), invert(node.left)). Same O(N) time, same O(H) recursion space, plus O(N) for the new nodes. State this distinction aloud — it shows production awareness.

Iterative variants — when and why:

• BFS (queue): visit level by level, swap children at each node, enqueue both children. Natural for level-by-level operations.
• DFS (stack): push root, pop, swap children, push both. Slightly different traversal order from recursion but same final result (because swap commutes).
• Why iterative matters: Python’s default recursion limit is 1000. A tree of depth 1500 will RecursionError. Iterative BFS uses heap-allocated deque — no stack overflow. Real interviewer follow-up: “Now the tree has depth 10^5. Recursion won’t work — rewrite.”

The Max Howell story is the cultural pretext: Google rejected the creator of Homebrew (then the world’s most popular macOS package manager) for not solving this on a whiteboard. The interviewer was wrong to gatekeep this hard, BUT the story made the problem famous, and now every shop asks it. Don’t fail it.

Connection to mirror-walk family:

• LC 101 (Symmetric Tree, p15): check if a tree is its own mirror. The check is “is left the mirror of right?” — same algorithm, only walks both sides simultaneously without mutation.
• LC 951 (Flip Equivalent): are two trees equivalent under any sequence of child-flips? Recursion: equiv(a,b) = (a.val==b.val) AND (equiv(a.left,b.left) AND equiv(a.right,b.right) OR equiv(a.left,b.right) AND equiv(a.right,b.left)).

7. Anti-Pattern Analysis

Wrong-but-tempting #1 — Forgetting the null base case:

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

Crashes immediately on the recursive call into a None child. The fix: if node is None: return None as the FIRST line.

Wrong-but-tempting #2 — Swapping references but not recursing:

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

Only swaps the root’s children. The subtrees are NOT inverted. Test with depth-3 tree.

Wrong-but-tempting #3 — Recursing but not swapping at the current level:

def invert(node):
    if not node: return None
    invert(node.left)
    invert(node.right)
    return node

Inverts each subtree’s internals but never swaps left/right at any level. Returns the original tree unchanged.

Wrong-but-tempting #4 — Two-step “save then swap” with the wrong order:

left = node.left
node.left = invert(node.right)
node.right = invert(left)

This is actually correct (and equivalent to the tuple-swap version) but visually confusing. Prefer the tuple swap; it’s atomic and idiomatic.

Wrong-but-tempting #5 — Iterative DFS with for over children list mid-mutation:

stack = [root]
while stack:
    node = stack.pop()
    if not node: continue
    for child in (node.left, node.right):
        stack.append(child)
    node.left, node.right = node.right, node.left

Subtle: for child in (node.left, node.right) evaluates the tuple BEFORE the swap, so children are pushed correctly. Easy to bug by swapping FIRST then pushing — works equivalently but visually inverted. State which order you chose.

8. Skills & Takeaways

Generalizable patterns:

• “What does this function return for a subtree?” — universal tree-recursion framing. Apply to every tree problem.
• Base case first. Every tree recursion’s line 1 is if not node: return <base>.
• Iterative tree traversal with deque/stack — must be reflex for the “recursion overflow” follow-up.
• In-place vs. new-tree contract — clarify with interviewer; production often forbids mutation.

Analogous problems:

• LC 100 — Same Tree (p13): walks two trees in parallel, returns bool.
• LC 101 — Symmetric Tree (p15): walks one tree as if it were two mirrored sides.
• LC 572 — Subtree of Another Tree: is_subtree(s, t) = is_same(s, t) OR is_subtree(s.left, t) OR is_subtree(s.right, t).
• LC 617 — Merge Two Binary Trees: same pattern but on two trees with value-summing.
• LC 951 — Flip Equivalent Binary Trees: invert-or-don’t recursion.
• LC 1325 — Delete Leaves with Given Value: post-order mutation (must recurse first, then check leaf).

When NOT to recurse: when tree depth may exceed ~1000 (Python recursion limit). Switch to iterative BFS or DFS-stack.

9. When to Move On (binary; must all be YES)

• I wrote the recursive version cold in <3 min, with if not node: return None as line 1.
• I wrote the iterative BFS version cold in <5 min.
• I can articulate “this function returns the inverted subtree’s root” before coding.
• I can convert to non-mutating form (returns a new tree) on request.
• My stress_test() cross-checks recursive vs iterative on 1000 random trees.
• I can answer “what if depth is 10^5?” without panic (iterative + sys.setrecursionlimit for recursive variant).
• I solved LC 101 (Symmetric Tree) and recognized it as the same algorithm walking two pointers.
• I know the Max Howell story and can explain why iterative variant matters in production.

If any unchecked: redo before moving to p12.

10. Company Context

Google (extremely common; THE question)

• The framing: The Max Howell question. Straight problem.
• Misleading example: Often a depth-3 perfectly balanced tree. The recursive 4-liner works trivially.
• Adversarial extension: “Now do it iteratively.” (BFS deque or DFS stack.) Then: “Now without mutating the input.” (Build a new tree.) Then: “Now the tree has depth 10^5.”
• What they want to hear: Both recursive AND iterative ready. Explicit “I’ll mutate in place since the contract allows; here’s the non-mutating variant if needed.”

Amazon (high frequency; phone screen warmup)

• The framing: Straight problem, often paired with a second harder question.
• Misleading example: Includes a null child early to test base case discipline.
• Adversarial extension: “Now invert ONLY the bottom K levels.” Then: “Now invert in-place AND return the original tree (deep-copy first).”
• What they want to hear: Confident recursion with base case; clean iterative pivot.

Microsoft (high frequency)

• The framing: Straight, in C++ for systems roles or Python/Java for SWE.
• Adversarial extension: “Now do it without recursion AND without an explicit stack/queue.” (Morris-traversal-style — Hard; usually only Staff-track interviews go here.)
• What they want to hear: Recursion as default, BFS/DFS-stack as fallback, awareness that Morris traversal exists for O(1) extra space.

Meta (medium; usually as warmup to LC 100/101 chain)

• The framing: Followed by p13 (Same Tree) and p15 (Symmetric Tree) in rapid succession.
• What they want to hear: Recognition that these three problems share the parallel-tree-walk pattern. Pivot fluidly.

Apple, Bloomberg (medium)

• The framing: Standard.
• What they want to hear: Clean code; both recursive and iterative; clear base case.

11. Interviewer’s Lens

The scorecard line that gets you the offer: “Recursive in <2 min, iterative in <4 min, articulated base case before coding, handled the 10^5 depth follow-up cleanly.”

The scorecard line that loses you: “Got stuck on the iterative variant; couldn’t explain why depth matters.”

12. Level Delta

13. Follow-up Questions & Full Answers

Follow-up 1: “Do it iteratively.”

Signal sought: Iterative tree traversal reflex.

Full answer: “BFS with collections.deque. Enqueue root; while queue nonempty, dequeue a node, swap its children, enqueue both children (skipping None). O(N) time, O(W) space where W is max width (up to N/2 for the last level of a complete tree). DFS stack alternative works identically — push root, pop, swap, push children. I’d prefer BFS for level-by-level operations and DFS-stack when memory is tighter on wide trees.”

Follow-up 2: “Without mutating the input.”

Signal sought: Awareness of mutation contract.

Full answer: “Build a new tree. def invert_pure(node): if not node: return None; return TreeNode(node.val, invert_pure(node.right), invert_pure(node.left)). Note the recursion arguments are swapped in the constructor — right goes into the new left child slot. Same O(N) time and O(H) recursion depth, plus O(N) for the new tree allocation. Required when the original tree is shared (e.g., immutable persistent structure in a multi-threaded context).”

Follow-up 3: “Tree has depth 10^5 — recursion overflows.”

Signal sought: Production-language awareness.

Full answer: “Two options. (a) sys.setrecursionlimit(200_000) — works for Python but expensive: each stack frame is ~500 bytes, so depth 10^5 uses ~50MB just for the call stack. (b) Iterative BFS or DFS-stack — heap-allocated, no stack-frame overhead. I’d default to iterative for any depth above ~1000. In Java the equivalent is -Xss JVM flag; in Go, goroutine stacks auto-grow; in Rust, you’d write iterative because stack overflow is a hard abort with no graceful recovery.”

Follow-up 4: “Now invert only the bottom K levels.”

Signal sought: Adapt recursion to a depth parameter.

Full answer: “Pass a level parameter (root = 0). Compute total depth first (one pass) to know the cutoff: cutoff = total_depth - K. Then a second pass: if level >= cutoff, swap; recurse with level + 1. Or, more elegantly: recurse first to compute height-from-bottom; on the way back up, swap if height_from_bottom < K. Single pass, post-order, O(N) time.”

Follow-up 5 (Staff signal): “Verify two trees are inversions of each other (without actually inverting).”

Signal sought: Generalization to LC 101’s pattern.

Full answer: “Walk both trees in parallel: def are_inversions(a, b): if a is None and b is None: return True; if a is None or b is None: return False; return a.val == b.val and are_inversions(a.left, b.right) and are_inversions(a.right, b.left). The cross-recursion (a.left vs b.right) is the inversion check. O(N), O(H). This IS the algorithm for LC 101 (Symmetric Tree) generalized to two distinct trees.”

14. Full Solution Walkthrough

See solution.py.

The file has six sections:

1. TreeNode — __slots__ = ("val", "left", "right") for memory efficiency.
2. invert_recursive(node) — 4-line classic; base case first.
3. invert_iterative_bfs(node) — collections.deque; level-by-level.
4. invert_iterative_dfs(node) — explicit list as stack.
5. invert_pure(node) — non-mutating variant; builds new tree.
6. stress_test() — builds 1000 random trees with random.Random(42); verifies all four implementations produce the same result (via deep equality on serialized form).
7. edge_cases() — empty, single, left-only-skewed, balanced, right-only-skewed.

Decisions justified:

• Why tuple swap (node.left, node.right = invert(node.right), invert(node.left)): atomic, idiomatic, equivalent to save-then-swap.
• Why __slots__: a million-node tree saves ~50MB.
• Why we serialize trees for equality check (in stress_test): structural equality of mutable trees requires either parallel-walk or canonical serialization; we use the latter to also exercise level-order encoding.

15. Beyond the Problem — Production Reality

Where this exact algorithm shows up:

• Compiler IR transformations: many AST rewrite passes are exactly “walk the tree, mutate each node.” Inverting a tree is a tiny special case of a larger family.
• Database query plan rewrites: Postgres’ query planner walks the plan tree and rewrites nodes (predicate pushdown, join reordering). Iterative because plan trees can be very deep.
• Game-tree pruning (minimax): alpha-beta is a recursive tree walk; in some implementations the tree is mirrored when switching between max-player and min-player perspectives.
• UI rendering: React’s virtual DOM reconciliation walks a tree and mutates. Mostly iterative for the same depth reasons.

Production caveats:

• Thread safety: in-place mutation is NOT thread-safe. If the tree is shared (read-only) across threads, you MUST use the non-mutating variant.
• Persistent data structures: in functional languages (Clojure, Haskell, OCaml), all tree updates are non-mutating by default — you return a new tree sharing unchanged subtrees. This is structural sharing; the non-mutating variant above is the entry point.
• GC pressure: the non-mutating variant allocates N new nodes per inversion. For trees of millions of nodes, this can trigger GC pauses. In-place mutation is preferred when allowed.
• Recursion limits: as noted, depth >1000 in Python requires setrecursionlimit or iterative rewrite. The pattern of “default to recursive, fall back to iterative when depth grows” is universal across tree algorithms.

Principal-engineer code review comment: “Recursive invert is fine for our render tree (max depth ~50). But our query planner has trees up to 1500 deep on complex multi-join queries — we hit RecursionError in prod last quarter. Switched to iterative DFS-stack. PR comment to future: any tree-walk on user-supplied data MUST be iterative. Cost of the deque allocation is negligible vs. the cost of a SIGSEGV-equivalent crash on the request thread. Add a lint rule that flags def visit_node(...) without a corresponding iterative variant for trees with unbounded depth.”