L25 · Trees IV — Paths & Accumulators

Series: LeetCode — From Basics to Interview-Ready · Session 25 / 65 · Phase 1 · Core patterns

Why this session exists

This is the return-one-thing-track-another pattern, and it is core to many tree Hards.

Here is the difficulty it exists to resolve. In Diameter of Binary Tree, the longest path might pass through the root, or it might live entirely inside one subtree and never touch the root at all. So the answer at a node is not a function of the answers at its children — a child's diameter tells you nothing about paths that pass through this node. You need something else from the child: its height.

That is the whole insight. The recursion returns what the parent needs to do its own computation, and a separate variable accumulates what the problem actually asks for. Two different quantities, deliberately kept apart. Once you name that distinction, Diameter, Binary Tree Maximum Path Sum, Longest Univalue Path, and House Robber III all become the same shape.

People get stuck here because they try to make one value do both jobs. If the function returns the diameter, the parent cannot combine children's diameters into anything meaningful. If it returns the height, the diameter has nowhere to live — unless you put it somewhere outside the return chain. Hence the accumulator.

Blank-file warm-up

Five minutes, empty file, no notes. Write the skeleton:

best = 0

def dfs(node):
    ...
    nonlocal best
    best = max(best, ...)
    return ...

Fill it in for Diameter of Binary Tree, and then write two separate sentences: "the return value is ___, because the parent needs it to ___" and "the accumulator holds ___, because that is what the problem asks for".

If you cannot write those two sentences separately, you have not separated the two quantities yet — and that separation is the entire session.

Pattern anatomy

The shape that summons this pattern: an optimum over all paths or subtrees, where the optimum is not required to include the root.

The invariant, stated as two clauses:

dfs(node) returns the best value for a path that starts at node and goes downward only — a quantity its parent can extend. Meanwhile the accumulator records the best value for any path anywhere in the subtree processed so far, including paths that turn at node and therefore cannot be extended upward.

The word "turn" is doing real work there. A path that goes up from the left subtree, through node, and down into the right subtree has used node as an apex. Its parent cannot extend it, because doing so would visit node twice. So that value must be recorded, not returned.

def diameter_of_binary_tree(root):
    best = 0
 
    def height(node):
        nonlocal best
        if not node:
            return 0
        left = height(node.left)         # edges below on the left
        right = height(node.right)       # edges below on the right
        best = max(best, left + right)   # path TURNING here — record it
        return 1 + max(left, right)      # path going DOWN — return it
 
    height(root)
    return best

Six lines of body, and the two crucial ones sit adjacent so the contrast is visible. left + right is the path that comes up one side and goes down the other. 1 + max(left, right) is the path the parent can use — one side only, plus the edge up to node.

Maximum Path Sum is the same skeleton with two adjustments:

def max_path_sum(root):
    best = float('-inf')                 # values may be negative
 
    def gain(node):
        nonlocal best
        if not node:
            return 0
        left = max(gain(node.left), 0)   # clamp: a negative branch is not worth taking
        right = max(gain(node.right), 0)
        best = max(best, node.val + left + right)   # turn here
        return node.val + max(left, right)          # extend upward
 
    gain(root)
    return best

The clamp is the new idea. When a subtree's best downward path sums to a negative number, including it makes things worse, so you take zero instead — meaning "do not extend into that subtree at all". Writing max(gain(node.left), 0) expresses that in one place and keeps both the accumulator line and the return line clean.

The initial value must be -inf, not 0. If every node is negative, the answer is the single largest node value, and initialising the accumulator to 0 would return 0 — a path that does not exist. That is the single most common wrong submission on this problem.

Path Sum, by contrast, is the simple case where the answer is just a return value:

def has_path_sum(root, target):
    if not root:
        return False
    if not root.left and not root.right:        # leaf
        return root.val == target
    rest = target - root.val
    return has_path_sum(root.left, rest) or has_path_sum(root.right, rest)

No accumulator needed, because every path here starts at the root and ends at a leaf — there is no turning. It is worth solving alongside the other two precisely to feel the difference: when paths are anchored at the root, plain recursion suffices; when they can start and end anywhere, you need the two-quantity split.

The cue

How you recognise this from the problem statement:

1. "Any path", "the path may or may not pass through the root", "between any two nodes". This phrasing is nearly diagnostic. Unanchored paths mean an accumulator.
2. "Maximum" or "longest" over a tree, where the answer is a path rather than a node. Diameter, max path sum, longest univalue path.
3. A node's answer cannot be built from its children's answers. If you try to write the recurrence and find the children's values are the wrong type of information, you need to return something else and accumulate the real answer separately.
4. The problem asks for one global number, not a per-node result. A single scalar answer over a whole tree is what an accumulator is for.
5. "Turning point", "apex", "V-shape". Any path that goes up and then down has an apex node, and the apex is where you record.

The anti-cue: if every valid path starts at the root — Path Sum, root-to-leaf enumeration, sum of root-to-leaf numbers — the return value alone is enough and an accumulator is unnecessary machinery. And if the problem wants all such paths rather than the best one, that is backtracking, which is a later session.

Guided solve

Diameter of Binary Tree. Return the length of the longest path between any two nodes, measured in edges. The path may or may not pass through the root.

Start by trying the obvious recurrence and watching it fail, because that failure motivates everything else.

Attempt: diameter(node) = max(diameter(left), diameter(right), something_through_node). The first two terms are fine — the longest path might be entirely inside a subtree. But what is something_through_node? It is the deepest reach into the left plus the deepest reach into the right. And diameter(left) does not tell you the left subtree's depth; a subtree can have a large diameter and a small height, or the reverse. The information you need is simply not in the return value.

So: return the height, which is what the parent needs, and put the diameter somewhere else.

Precisely:

• Return 1 + max(left_height, right_height) — the longest downward-only path from this node, in edges, which the parent can extend by one.
• Accumulate left_height + right_height — the longest path that turns at this node, which no ancestor can extend.

Every possible path in the tree turns at exactly one node — its highest point. So by considering the turn at every node, you consider every path exactly once. That is the completeness argument, and it is worth saying out loud.

Trace this tree:

      1
     / \
    2   3
   / \
  4   5

height(4): both children null, both return 0. best = max(0, 0 + 0) = 0. Return 1 + 0 = 1.

height(5): identical. best stays 0. Return 1.

height(2): left = 1 (node 4), right = 1 (node 5). Turn at 2 gives 1 + 1 = 2, so best = 2. Return 1 + max(1, 1) = 2.

height(3): leaf. Return 1. best unchanged at 2.

height(1): left = 2 (node 2), right = 1 (node 3). Turn at 1 gives 2 + 1 = 3, so best = 3. Return 1 + max(2, 1) = 3.

Answer: 3. Verify by hand — the path 4 → 2 → 1 → 3 has three edges. Correct. So does 5 → 2 → 1 → 3. Both are length 3.

Now the case that separates this from a naive solution. Consider a tree whose root has a long left spine and whose right subtree is a small but wide bush:

        1
       / \
      2   6
     /   / \
    3   7   8
   /
  4

The longest path is 4 → 3 → 2 → 1 → 6 → 7, five edges, and it does pass through the root. Fine. But now hang a deep balanced subtree off node 8 and the longest path can end up entirely inside it, never touching the root. The accumulator catches it because it is updated at every node, not only at the root. A solution that computes left_height + right_height only at the root gets this wrong, and it is a mistake that survives all the small test cases.

Solo timed

15 minutes each, timer visible.

• Path Sum — subtract as you descend, check the remainder at leaves. No accumulator. Be careful that a leaf is a node with no children, not a node with one null child.
• Binary Tree Maximum Path Sum — clamp negative branch gains to zero, initialise the accumulator to negative infinity, and keep the turn line and the return line adjacent so the difference stays visible.

If you finish early: solve Longest Univalue Path, where a child only contributes to the extension if its value equals the current node's. It is the same skeleton with a conditional on the contribution.

Common failure modes

Returning the accumulated answer instead of the extendable value. The parent then receives a diameter when it needed a height, and there is no way to recover. This is the defining mistake.

Initialising the accumulator to zero on a signed problem. Maximum Path Sum with all-negative values returns 0, which corresponds to no path at all. Use float('-inf').

Forgetting the negative clamp. Without max(gain(child), 0), a deeply negative subtree drags down the answer even though the correct move is simply not to go there.

Off-by-one between edges and nodes. Diameter counts edges, some variants count nodes. One convention gives 0 for a single node, the other gives 1.

Missing nonlocal. Assigning to best inside the nested function creates a new local binding and the outer variable never changes. Python's scoping makes this silent — the function runs fine and returns the initial value.

Updating the accumulator only at the root. Catches paths through the root and misses everything else. Update at every node.

Testing leaves incorrectly. if not node.left and not node.right is a leaf. Checking only one side treats a node with a single child as a leaf, which breaks Path Sum on unbalanced inputs.

Complexity

Time: O(n). A single postorder traversal visiting each node exactly once, with O(1) work per node — two comparisons and two arithmetic operations. Neither the accumulator update nor the return computation depends on subtree size, because both consume only the two already-computed child values.

That last point deserves emphasis. A solution that computes the height inside the diameter recursion — calling a separate height() function at every node — is O(n²), because each height call is itself O(size of subtree). Computing height and diameter in the same pass is what keeps it linear. If your solution has two nested traversals, that is the bug.

Space: O(h). One stack frame per node on the current root-to-node path. O(log n) for a balanced tree, O(n) for a skewed one. The accumulator itself is a single variable, O(1).

For Maximum Path Sum the bounds are identical. The clamping and the negative infinity initialisation cost nothing asymptotically.

Spaced queue

Re-solve whatever is due before starting anything new today. Status ladder:

• cold — solved unaided, first attempt clean → next review in 60 days
• warm — solved but slowly or with a stumble → 21 days
• hint — needed a nudge to get started → 7 days
• failed — could not produce a working solution → 2 days, then 7 days

Diameter and Maximum Path Sum both enter today. Grade Maximum Path Sum harder — it adds the negative clamp and the infinity initialisation on top of the same skeleton, and getting the skeleton right while missing either of those is still a wrong submission.