Trees IV — Paths & Accumulators

Review boundary and corrected contracts

height(None)=0 and height(node)=1+max(children) count nodes in a downward branch; left+right then counts edges on the diameter through the parent. Maximum path sum clamps negative child contributions but keeps a nonempty path and initializes the optimum at −infinity.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Separate what a recursion returns to its parent from what it records globally, so that path problems where the answer need not pass through the root become routine.

Series: LeetCode — From Basics to Production-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. Diameter, Maximum Path Sum, and Longest Univalue Path use this extendable-versus-global split. House Robber III instead returns two conditional subtree totals; the quiz contrasts that related tree-DP pattern.

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. This is an incomplete inner-function skeleton: place it inside an enclosing solver so nonlocal best has a function-scope binding. Then fill in the base case and recurrence:

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)         # nodes in left downward branch
        right = height(node.right)       # nodes in right downward branch
        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) counts nodes in a downward branch starting at node. When its parent uses that height, the same number counts edges from the parent down that branch.

Maximum Path Sum assumes a nonempty tree of integer values; an empty tree has no admissible path and is outside this function's contract. It 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 three-node chain and a three-node root with two leaf children both have diameter 2, but their node-heights are 3 and 2. Diameter alone does not determine height.

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

Precisely:

• Return 1 + max(left_height, right_height) — node-height of the longest downward branch starting here (a leaf returns 1).
• Accumulate left_height + right_height — the longest path that turns at this node, which no ancestor can extend.

Every simple path has a unique highest node. Group paths by that apex: the longest path in a group uses the deepest branch on each available side. The recurrence evaluates one best candidate per apex, not all O(n²) endpoint pairs. Taking the maximum of those n candidates therefore finds the global diameter.

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. For a concrete off-root case, take a new root R with only one child A, and give A two downward arms of three edges each. The best path through A has six edges; the longest path starting at R has only four. The accumulator catches the six-edge answer because it is updated at every node, not only at R. 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.

Edges versus nodes is the trap on this specific problem. LeetCode's Diameter counts edges, so a single node has diameter 0 and the base case returns 0 for an empty subtree. Longest Univalue Path also counts edges. Maximum Path Sum counts node values, so its base contributes 0 to a sum rather than 0 to a length. Read the problem's definition before choosing the base value — the two conventions differ by exactly one at every level, and a solution that is uniformly off by one usually means this was skipped.

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. In the shown best = max(best, ...) line, assigning makes best local, but the right-hand side reads it before that local is bound: Python raises UnboundLocalError. An assignment that never reads the old value could silently shadow it, but that is not this code.

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.

Myth: If a recursive function needs to track a global best, that means the design is wrong — a clean recursion should return everything it needs in its return value.

Why: Sometimes a single return value genuinely cannot carry both quantities, and forcing it to produces worse code, not better. In Diameter, the parent needs the child's height while the problem wants the diameter, and these are different numbers that cannot be recovered from one another. You could return a tuple (height, diameter) and thread it upward, which is legitimate and side-effect-free — but it makes every call site unpack two values and the combine step noticeably noisier. The accumulator keeps the return type simple and the recurrence readable. This is a deliberate trade, not a failure of design.

Steps 1: Every simple path has a unique highest node. For each possible apex, combine the best eligible branch on each side; one optimal candidate per apex suffices.

Steps 2: A candidate using both child branches cannot also extend upward without branching or revisiting the apex. A candidate with only one branch can extend; the separate return value selects the best such extendable branch.

Steps 3: Because a parent can only extend a path that descends through one subtree, the return value must be the best single-branch downward path, which is a different quantity from the turning path.

Steps 4: Because those two quantities are not recoverable from one another, one return value cannot serve both purposes — hence a separate accumulator or an explicit tuple return.

Steps 5: A postorder traversal evaluates one best turning candidate per node in O(1) work, rather than enumerating every path; total time is O(n).

Steps 6: Testable prediction: on the tree with root 1, children 2 and 3, and node 2 having children 4 and 5, the answer is 3 edges via 4-2-1-3. If your solution returns 2, it is accumulating only the return value and never the turning path.

Picture: Every path over a tree is an upside-down V with an apex. Standing at each node you measure how far you can reach down each side; their sum is the V that peaks right here, and the longer single side is all you can hand to whoever stands above you.

Trigger: Fires on 'any path', 'may or may not pass through the root', 'between any two nodes' — the moment paths stop being anchored at the root.

Name: Nonlocal accumulator plus a simple return

Gain: The return type stays a single number, the recurrence reads cleanly, and every call site is one line. It is the version most reviewers expect and the easiest to explain aloud.

Cost: The inner helper mutates a closure-local accumulator. Each outer invocation has its own best, so independent calls do not share that state. Omitting nonlocal from the shown read-then-write update raises UnboundLocalError.

Name: Return a tuple of (extendable, best_so_far)

Gain: Purely functional with no shared mutable state, thread-safe, and trivially testable at any node since everything the caller needs is in the return value.

Cost: Every call site unpacks two values and the combine step must merge both components, which roughly doubles the body and makes the core recurrence harder to see.

Name: Two separate traversals — compute all heights, then all turning values

Gain: Each pass does one thing and is individually simple to write and verify; useful when the two quantities are genuinely unrelated.

Cost: Requires storing per-node heights in a map, costs O(n) extra space, and doubles the traversal work for a result the single-pass version gets for free.

Pick: Use the nonlocal accumulator when writing Python under design review time pressure — it is the shortest correct version and the one your reviewer is expecting. Switch to the tuple return when the code must be side-effect free, for instance if the traversal will be parallelised or if the language makes closure mutation awkward.

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.

Self-check (answer follows each question).

Q: In Diameter of Binary Tree, what does the recursive function return and what does the accumulator hold?

A: It returns node-height, 1 + max(left, right), with a leaf returning 1. The accumulator holds the maximum edge count left + right over all apex nodes. A two-sided path cannot extend to the parent; the height return retains only one side.

Q: Why can't a node's diameter be computed from its children's diameters?

A: Diameter does not determine height: a three-node chain and a root with two leaf children both have diameter 2, but node-heights 3 and 2. The parent needs those heights to combine branches through itself.

Q: Why must Maximum Path Sum initialise the accumulator to negative infinity rather than zero?

A: If every node value is negative, the correct answer is the single largest (least negative) node. Initialising to zero returns 0, which corresponds to an empty path that the problem does not permit.

Q: What does max(gain(node.left), 0) express, and why is it correct?

A: It means 'do not extend into this subtree if doing so would reduce the total'. A branch whose best downward sum is negative can always be omitted, and clamping to zero encodes that choice in one place rather than branching later.

Q: Why is calling a separate height() function inside the diameter recursion O(n²)?

A: Each height call traverses its entire subtree, so the work at a node is proportional to its subtree size, and summing that over all nodes gives O(n²) on a skewed tree. Computing height and diameter in the same postorder pass reuses each child's height once and keeps it linear.

Q: House Robber III forbids robbing two directly connected houses in a tree. How does the return-one-track-another idea apply, and what changes?

A: The recursion returns a pair rather than a scalar: the best total for this subtree assuming the node is robbed, and the best assuming it is not. The robbed case is node.val plus both children's not-robbed values; the not-robbed case is the sum over children of max(robbed, not_robbed). At the root return max(robbed, not_robbed). No separate global accumulator is needed: the parent needs conditional subtree totals, not only the larger unconditional total.

Stretch: true

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.

• Return what the parent can use; accumulate what the problem asks for. They are different quantities and neither can be recovered from the other.

• Every path has a unique highest node; evaluate the best candidate for each apex, not every endpoint pair.

• A path using both child branches cannot extend upward. Return only the best single branch; record the combined candidate.

• Clamp negative contributions to zero: a branch that hurts the total should simply not be taken.

• Initialise the accumulator to -inf on signed problems; zero silently returns a path that does not exist.

• Compute height and the answer in the same pass. Calling a separate height() per node makes it O(n²).

Corrective source notes

• CPython v3.14.0 execution model — local read-before-binding raises UnboundLocalError; nonlocal refers to an enclosing function binding. Checked 2026-10-09. The diameter and gain recurrences are proved above and checked against finite all-pairs path oracles, not attributed to the generic DFS reference.

• Depth First Search - Algorithms for Competitive Programming — DFS explores a graph through recursive or explicit-stack expansion. Checked 2026-10-07.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.