p12 Max Depth — Progressive Hints

Rule: ONE hint at a time, 5-min timer between.

Hint 1 — Pattern

What does “depth of a tree” mean in terms of the depths of its left and right subtrees? Write the relation in plain English.

Hint 2 — Base case

What’s the depth of an empty tree? (Hint: 0.) What’s the depth of a single-node tree? (1 — the root counts.)

Hint 3 — The recurrence

depth(node) = 1 + max(depth(left), depth(right))

The +1 counts the current node; we add it to the deeper of the two subtrees.

Hint 4 — Pseudocode

Recursive:

def depth(node):
    if node is None: return 0
    return 1 + max(depth(node.left), depth(node.right))

BFS (level-by-level):

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

Hint 5 — Full + traps

Time O(N), space O(H) (recursive) or O(W) (BFS).

Trap 1 — placing +1 wrong: max(1 + ..., 1 + ...) works (each side adds its own root); 1 + max(...) is cleaner. Both correct; the latter is idiomatic.

Trap 2 — BFS without len(queue) snapshot: if you increment depth on every pop, you count NODES not LEVELS. The snapshot pins the level boundary.

Trap 3 — DFS with stack: must carry the depth as (node, depth) pair; len(stack) is unrelated to path length.

Trap 4 — Don’t transplant to LC 111 (min depth): the symmetry breaks for nodes with one missing child. A node with left=None, right=non-empty is NOT a leaf — its depth-to-nearest-leaf goes through the right subtree, not 0.

Why this matters beyond this problem: the recurrence f(node) = combine(node.val, f(left), f(right)) is the template for EVERY “compute an integer/property of a tree” problem. Internalize the template.