p12 — Maximum Depth of Binary Tree

Source: LeetCode 104 · Easy · Topics: Tree, DFS, BFS, Binary Tree Companies (2024–2025 frequency): Amazon (very high), Microsoft (high), Apple (high), Bloomberg (medium), Meta (medium), Google (medium) Loop position: phone screen warmup; often paired with LC 111 (Min Depth) or LC 110 (Balanced).

1. Quick Context

This is the canonical “function returns an integer aggregate from children” problem. The recursion: depth(node) = 1 + max(depth(left), depth(right)) with base case depth(None) = 0. It’s the foundational template for height, sum, count, max-value, and dozens of other tree-aggregation problems. Mastery here makes LC 110 (Balanced), LC 543 (Diameter, p14), LC 124 (Max Path Sum), and the entire DP-on-trees family trivial.

Mid candidates write it. Senior candidates write it AND the iterative BFS version AND explain why level-by-level matters. Staff candidates connect it to LC 110 (height check that’s O(N) instead of O(N²)) and LC 111 (subtle min-depth trap: a node with one missing child is NOT a leaf).

What it looks like it tests: compute height. What it actually tests: can you write “aggregate-from-children” recursion as reflex? Can you pivot to BFS for level-by-level reasoning?

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/maximum-depth-of-binary-tree/

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

3. Prerequisite Concepts

• TreeNode and binary tree mental model (phase-01 §9)
• Recursion with integer return type (phase-01 §8)
• BFS with collections.deque for level-by-level counting
• The “post-order aggregate” pattern: compute children’s values, then combine

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

Step 1 — Restate: “Given the root of a binary tree, return the number of nodes along the longest path from the root down to the farthest leaf.”

Step 2 — Clarify:

• “Empty tree → 0?” (Yes per LC.)
• “Single node — depth 1 or 0?” (1 per LC; the single node IS the root AND a leaf.)
• “Path counts NODES or EDGES?” (Nodes per LC. Some problems count edges — always ask.)
• “Max recursion depth I should worry about?” (LC says up to 10^4 — RecursionError risk in Python without setrecursionlimit.)
• “All-left or all-right skewed input expected?” (Possible; pushes recursion depth to N.)

Step 3 — Constraints: N up to 10^4 per LC. O(N) time required (must visit every node to know the depth). Recursion space O(H) for height-H tree; can be O(N) for skewed.

Step 4 — Examples:

• [3,9,20,null,null,15,7] → 3.
• [] → 0.
• [1] → 1.
• [1,null,2,null,3,null,4] (right-skewed) → 4.
• Balanced tree of N=15 (depth 4) → 4.

Step 5 — Brute Force: Recursion IS the natural form. “Brute force” alternative: enumerate every root-to-leaf path, return max path length. Same O(N) time but messier code.

Step 6 — Complexity: O(N) time (touch every node). Space O(H) recursion stack OR O(W) BFS queue (W = max width, up to N/2 for the bottom level of a complete tree).

Step 7 — Pattern Recognition: “Compute an integer aggregate over a tree” → post-order DFS (combine children’s results at the current node). Iterative alternatives: BFS counting levels; DFS-stack with explicit (node, depth) pairs.

Step 8 — Optimize: Already optimal. The “optimization” question is the iterative variant for stack-safety on deep trees.

Step 9 — Prove correctness: Induction on tree size. Base: empty tree has depth 0. Inductive step: assume function correct on trees of size < N. For tree of size N with root r: left subtree (size < N) returns depth_L; right subtree returns depth_R. By definition, the longest root-to-leaf path either goes through left or through right; its length is 1 + max(depth_L, depth_R). Correct.

5. Progressive Hints

If stuck for 5 minutes, open hints.md.

6. Deeper Insight — Why It Works

The “aggregate-from-children” template: any tree problem of the form “compute an integer property of a tree” follows this template:

def aggregate(node):
    if node is None: return BASE
    left_val  = aggregate(node.left)
    right_val = aggregate(node.right)
    return COMBINE(node.val, left_val, right_val)

For depth: BASE = 0, COMBINE = 1 + max(left, right). For node count: BASE = 0, COMBINE = 1 + left + right. For sum: BASE = 0, COMBINE = node.val + left + right. For max value: BASE = -∞, COMBINE = max(node.val, left, right). Internalize this template — it generalizes to LC 110, 543, 124, 543, 968, etc.

Why post-order (not pre-order): the combine step uses children’s results, so children must be computed first. Pre-order would compute the root before children — impossible when the answer depends on children.

Iterative BFS — counting levels: the depth equals the number of BFS levels traversed.

depth = 0; q = deque([root])
while q:
    depth += 1
    for _ in range(len(q)):
        cur = q.popleft()
        if cur.left:  q.append(cur.left)
        if cur.right: q.append(cur.right)
return depth

The for _ in range(len(q)) is critical: it snapshots the level’s size before any appends, so the inner loop processes exactly one level. Without it, the loop processes all queued nodes including children added during this level — degenerate to total-node-count, not depth. This is the “snapshot-level-size” pattern; reappears in LC 102, 199, 103.

Iterative DFS — (node, depth) pairs:

stack = [(root, 1)]; best = 0
while stack:
    node, d = stack.pop()
    if node is None: continue
    best = max(best, d)
    stack.append((node.left, d + 1))
    stack.append((node.right, d + 1))
return best

Carry the depth alongside the node. Equivalent to recursive but heap-allocated.

The LC 111 (Min Depth) trap — DON’T transplant the algorithm: min_depth(node) = 1 + min(min_depth(left), min_depth(right)) is WRONG when one child is None. A node with left=None, right=non-empty is NOT a leaf — its depth-to-leaf goes through the right subtree. The correct min-depth handles this: if one child is None, recurse only into the other. This is why LC 111 is “Easy” but trips many candidates — the symmetry with max-depth is broken by the leaf definition.

Production: tail recursion? Python doesn’t optimize tail calls, but the recursion isn’t tail-recursive anyway (1 + max(...) requires the recursive results before computing). Always iterative for deep trees in production.

7. Anti-Pattern Analysis

Wrong-but-tempting #1 — Forgetting the +1:

def depth(node):
    if not node: return 0
    return max(depth(node.left), depth(node.right))  # missing +1

Returns 0 for any tree. Add 1 + to count the current node.

Wrong-but-tempting #2 — Returning 1 from None:

if not node: return 1

Off-by-one: every leaf gets depth 2, root gets total-depth + 1. Base case for empty is 0.

Wrong-but-tempting #3 — BFS without level-size snapshot:

q = deque([root])
depth = 0
while q:
    cur = q.popleft()
    depth += 1   # WRONG: counts nodes, not levels
    if cur.left: q.append(cur.left)
    if cur.right: q.append(cur.right)

Returns total node count. Need the inner for _ in range(len(q)) loop to process one level at a time.

Wrong-but-tempting #4 — Using len(stack) as current depth:

stack = [root]
while stack:
    cur = stack.pop()
    best = max(best, len(stack))  # WRONG

len(stack) is the number of UNPROCESSED nodes, not the current path length. Always pair (node, depth) explicitly.

Wrong-but-tempting #5 — Transplanting to LC 111 without re-thinking:

def min_depth(node):
    if not node: return 0
    return 1 + min(min_depth(node.left), min_depth(node.right))  # WRONG

For a tree with only a right child, min(0, 1+...) returns 1 (root with phantom-leaf in the missing-left slot). But the root is not a leaf — actual min depth is 1 + (right's min depth). Always re-derive when symmetry is suspicious.

8. Skills & Takeaways

Generalizable patterns:

• “Aggregate-from-children” recursion — the template for ALL tree-DP problems.
• BFS level-by-level with size snapshot — reappears in LC 102, 103, 107, 199.
• (node, payload) stack pairs — the iterative equivalent of “carrying state through recursion.”

Analogous problems:

• LC 111 — Min Depth (subtle leaf-definition trap).
• LC 559 — Max Depth N-ary Tree (children list instead of left/right).
• LC 110 — Balanced Binary Tree (use depth recursion to early-exit on imbalance; the O(N) variant is “return depth or -1 if unbalanced”).
• LC 543 — Diameter (p14): same height computation, but accumulates a global max as a side effect.
• LC 124 — Max Path Sum: same template, but the “combine” allows skipping negatives.
• LC 222 — Count Complete Tree Nodes (Hard variant: O(log² N) using completeness).
• LC 366 — Find Leaves of Binary Tree (height-from-bottom is the level number).

When NOT to use recursion: depth > 1000 (Python). Use iterative BFS (counts levels) or DFS-stack with (node, depth) pairs.

9. When to Move On

• Recursive in <2 min, base case if not node: return 0 stated aloud.
• Iterative BFS with level-size snapshot in <4 min.
• Iterative DFS with (node, depth) pair in <4 min.
• I can explain why 1 + is on the OUTSIDE of max, not inside.
• My stress_test() cross-checks all three implementations.
• I solved LC 111 (Min Depth) and articulated why direct transplant is wrong.
• I sketched LC 110 (Balanced) using the “return depth or -1” trick.
• I see how this template generalizes to LC 543 and LC 124.

10. Company Context

Amazon

• The framing: Straight problem; or “given a folder tree, find the deepest path.”
• Adversarial extension: “Now return the actual path, not just length.” (Carry path as a list; return tuple of (depth, path).) Then “Now it’s a DAG, not a tree.” (Memoize.)
• What they want to hear: Recursive default + iterative on request + extension to N-ary trees.

Microsoft / Apple

• The framing: Straight problem; sometimes paired with LC 111 to test for the trap.
• What they want to hear: Clean recursion + handling of empty and skewed cases.

Bloomberg

• The framing: “Given a binary tree representing a financial hierarchy, find the longest reporting chain.”
• Adversarial extension: “Now the tree is N-ary (each manager has K reports).” (LC 559.)
• What they want to hear: Generalization to N-ary; iterative variant for deep org charts.

Meta

• The framing: Usually as warmup to LC 543 (Diameter) or LC 124 (Max Path Sum).
• What they want to hear: Recognition that depth/height is the building block; pivot smoothly to diameter when prompted.

Google

• The framing: Straight or “in a tree of compute jobs, find the critical path length.”
• What they want to hear: Both DFS and BFS variants; complexity analysis distinguishing balanced vs skewed.

11. Interviewer’s Lens

12. Level Delta

13. Follow-up Questions & Full Answers

Follow-up 1: “Iteratively, in BFS form.”

Full answer: “Use a deque. Initialize depth=0. While the queue is nonempty: increment depth, snapshot n = len(queue), then process exactly n nodes (each one’s children get appended for next level). Return depth. The len(queue) snapshot is critical — it pins the count BEFORE new appends, so the inner loop sees exactly one level. O(N) time, O(W) space.”

Follow-up 2: “Iteratively, in DFS form.”

Full answer: “Stack of (node, depth) pairs. Pop, update global max, push children with depth+1. Skip None children at push time or check on pop — both work. O(N) time, O(H) space.”

Follow-up 3: “Now compute the MIN depth (LC 111).”

Signal sought: spot the leaf-definition trap.

Full answer: “Cannot just swap max for min — a node with one missing child is NOT a leaf, so its ‘depth via missing side’ shouldn’t count. Correct: if both children None → return 1 (this IS a leaf). If only one child → return 1 + min_depth(that child). If both children → return 1 + min(min_depth(left), min_depth(right)). The asymmetric case (one child missing) breaks the symmetry with max-depth.”

Follow-up 4: “Now check if the tree is height-balanced (LC 110).”

Signal sought: combine depth check with structural invariant.

Full answer: “Naive: compute depth at every node, check |depth(left) - depth(right)| <= 1. O(N²) (depth is O(N), called for each of N nodes). Better: a single post-order pass returns either the depth OR a sentinel (-1) meaning ‘unbalanced’. As soon as any subtree returns -1, propagate -1 up. O(N) time. The trick: the height computation IS the balance check; we just augment to early-exit.”

Follow-up 5 (Staff signal): “Now compute the diameter (LC 543, our p14).”

Full answer: “Two-channel pattern. The recursive function returns the HEIGHT of the subtree (1 + max child height). As a side effect, at each node it computes left_height + right_height + 1 (or +0 if measuring edges) and updates a global best_diameter. This is the most important tree trick: function returns one thing while a closure-captured variable accumulates another. The diameter passing through node N is left_height + right_height; the function returns height for the parent to use. O(N) time, O(H) space.”

14. Full Solution Walkthrough

See solution.py. Six sections:

1. TreeNode with __slots__.
2. max_depth_recursive(node) — 3-line classic.
3. max_depth_bfs(node) — BFS with level-size snapshot.
4. max_depth_dfs_iter(node) — DFS stack with (node, depth) pairs.
5. stress_test() — 1000 random trees; recursive, BFS, DFS must agree.
6. edge_cases() — empty, single, left-skewed, right-skewed, perfect.

Decisions justified:

• BFS uses len(queue) snapshot — explicit comment about why.
• DFS pushes None-checking on the consumer side (cleaner code; no harm appending None and continuing).
• All three variants tested for equality on random trees; the stress test is the contract.

15. Beyond the Problem — Production Reality

Where this template shows up:

• CI/CD pipeline DAG depth — “what’s the critical path of this build?” Same recursion, on a DAG (need memoization).
• Filesystem directory depth — find . -type d -print walks the tree; computing max depth is the BFS-level version.
• HTML DOM depth — browser engines bound nested element depth (Chrome caps at ~1000) to prevent stack overflow during render. They use iterative BFS internally.
• Compiler AST depth checks — many compilers reject programs with AST nesting > N to prevent stack overflow during semantic analysis.
• Game tree analysis — minimax depth bounds; iterative-deepening DFS uses bounded depth as the search horizon.

Production caveats:

• Skewed trees from sorted input: building a BST from sorted data creates a depth-N tree. Always rebalance (AVL, red-black) or use sorted-array-to-BST construction.
• Recursion limits: Python defaults to 1000, JVM ~5000-10000 depending on stack size, Go grows the stack as needed, Rust crashes hard. Always iterative for user-supplied tree depth.
• Concurrent depth queries: if many threads measure depth on the same tree, iterative is cache-friendlier (single contiguous deque) than recursive (scattered stack frames).

Principal-engineer code review comment: “Recursive max-depth is fine for our config tree (max depth 5). NOT fine for our user-uploaded XML/JSON parser — we’ve seen 100k-deep adversarial inputs designed to cause stack overflow (a known DoS vector; CVE-2022-XXXX in libxml). All user-data tree walks are iterative. Bonus: when measuring max depth on potentially adversarial input, add an early-exit cap (if depth > MAX_ALLOWED: raise) to fail fast on attack inputs rather than walking the entire tree first.”