p14 Diameter — Progressive Hints

Rule: ONE hint at a time. This problem is famously hard despite the “Easy” label — take your time.

Hint 1 — Observation about paths

Every path in a tree has a unique HIGHEST node (the bend point). For that highest node, the path descends into the LEFT subtree on one side and the RIGHT subtree on the other. What’s the length of that path in terms of subtree heights?

Hint 2 — Candidate at each node

At each node N, the longest path bending at N = height(left subtree of N) + height(right subtree of N) (measured in edges). The answer is the MAX of this candidate over all nodes.

Why all nodes? Because the answer path bends at SOME node — could be any. So check every one.

Hint 3 — Naive O(N²)

Compute height at each node separately. That’s height = O(N) called at N nodes = O(N²). Works on small inputs, TLE on large. Can we do it in one pass?

Hint 4 — The Two-Channel Pattern

We’re already computing all heights bottom-up during a single post-order traversal. So as we compute each node’s height, we can simultaneously check the candidate-diameter at that node and update a global best.

The recursive function’s purpose splits:

  • Channel B (return value): height, used by the PARENT.
  • Channel A (side effect): update best = max(best, lh + rh) — the answer we actually want.

Pseudocode:

best = 0
def height(node):
    if node is None: return 0
    lh = height(node.left)
    rh = height(node.right)
    nonlocal best
    best = max(best, lh + rh)       # CHANNEL A
    return 1 + max(lh, rh)          # CHANNEL B
height(root)
return best

Hint 5 — Full + traps + family preview

Time O(N), space O(H).

Trap 1 — Returning diameter from the recursion: You can’t combine cleanly because the parent needs HEIGHT, not diameter. Either use nonlocal or return a tuple (height, best).

Trap 2 — Edges vs nodes: LC counts edges. lh + rh (where height counts nodes from this node down) gives edge-count of the bent path correctly because: lh + rh nodes outside the bend + 1 node at bend = lh+rh+1 nodes = lh+rh edges. ALWAYS ask “edges or nodes?” first.

Trap 3 — Only checking diameter through root: the path may bend at any node. The two-channel pattern checks at every node automatically — but if you write diameter(root) = height(root.left) + height(root.right) directly, you only check root. Wrong.

Trap 4 — Side-effect scoping bugs: if best is a local int and you write best = ... inside the inner function without nonlocal, you create a new local; outer best stays 0. Use nonlocal best (or wrap in a list best = [0] and assign best[0] = ...).

Family — the same template solves:

  • LC 124 Max Path Sum (Hard): return node.val + max(0, max(left_gain, right_gain)) clamped ≥ 0; side-effect node.val + max(0,lg) + max(0,rg).
  • LC 687 Longest Univalue Path: return single-side same-value chain; side-effect both sides.
  • LC 1372 Longest ZigZag: return TWO heights per node.
  • N-ary version: sum of TOP-TWO child heights (use heapq.nlargest(2, ...)).

This is the most reusable trick in tree problems. Internalize it.