Tree DP (Return One, Update Another)

What is this?

Imagine every employee in a company reporting one number to their manager — say, the length of the longest reporting chain beneath them. A manager with two reports cannot pass both numbers up; a chain through them can only continue in one direction. But the manager can notice that their two reports' chains, joined through them, form the longest chain in the whole company so far, and write that on the office whiteboard.

One number goes up. A different number goes on the whiteboard. That split is the entire technique.

💡 Fun fact: Path Sum III runs the machinery backwards. Instead of gathering information upward, it carries a running root-to-node sum downward and keeps a map of prefix sums seen along the current path — the identical trick as Subarray Sum Equals K, because a root-to-node path is an array. The one addition trees demand is that the map must be undone on the way back up, since a prefix belonging to one branch must not be visible to its sibling.

🔓 The 5 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: a parent can only continue through one child, but the best answer often joins both at a node. So return the single best contribution upward, and update a shared answer with the combination — two different expressions, computed at the same moment.

1. The skeleton

answer = 0                            # the whiteboard

def dfs(node):
    global answer
    if not node:
        return 0                      # the identity for whatever you're combining
    L, R = dfs(node.left), dfs(node.right)
    answer = combine(answer, L, R, node)   # may span both children
    return contribution(L, R, node)        # what a parent can extend

Everything in this chapter is that shape with combine and contribution swapped out. The design work is choosing them — and choosing the return type, which is where richer problems get interesting:

Largest BST Subtree is the clearest argument for rich return types. Checking BST-ness and measuring size separately means re-traversing every subtree, giving O(n²). Returning all four facts at once makes it one pass, because a parent can decide its own validity purely from what its children reported.

2. When the flow reverses

Not all information travels upward. Path Sum III passes a running sum down, along with a map of how many times each prefix sum has occurred on the current root-to-node path:

def dfs(node, running, counts):
    if not node: return 0
    running += node.val
    total = counts.get(running - target, 0)      # paths ending here
    counts[running] = counts.get(running, 0) + 1
    total += dfs(node.left, running, counts) + dfs(node.right, running, counts)
    counts[running] -= 1                          # UNDO before returning to the parent
    return total

That last line is the tree-specific part. Without it, a prefix recorded in the left branch stays visible while the right branch is explored, and paths are counted that do not exist.

3. A 30-second worked example (Distribute Coins)

Each node holds coins; every node must end with exactly one. A move transfers a coin along one edge.

        3
       / \
      0   0

leaf 0 (left):   surplus = 0 - 1 = -1   → needs one coin  → |−1| = 1 move
leaf 0 (right):  surplus = 0 - 1 = -1   → |−1| = 1 move
root 3:          surplus = 3 + (−1) + (−1) − 1 = 0
                                              total moves = 2

The insight is that the number of moves along an edge is the absolute surplus flowing through it — you never simulate a transfer. A subtree needing two coins forces two traversals of the edge above it, whatever order they happen in.

4. Where you'll actually meet this

• Resource balancing. Redistributing load across a hierarchy of nodes or teams, counting transfers, is Distribute Coins with different nouns.
• Compilers. Type checking and constant folding return a fact about each subtree while accumulating diagnostics globally — the same split.
• Financial rollups. Aggregating balances up an account hierarchy while flagging the largest compliant subtree.
• Network routing. Computing per-subtree demand to size links is the surplus calculation exactly.
• Query planners. Deciding whether a subtree of a plan satisfies a property (sorted, unique, indexable) needs the composite return type that Largest BST Subtree teaches.

5. Problems in this chapter

▶ Distribute Coins in Binary Tree

Move coins so every node holds exactly one, minimising moves. Return each subtree's surplus; accumulate abs(surplus) per edge.
Pattern: return a flow, accumulate its magnitude. Target: O(n) time, O(h) space.

▶ Path Sum III

Count downward paths summing to a target. Running prefix sum passed down, a count map, and the crucial undo on the way back up.
Pattern: prefix sums on a path + backtracking the map. Target: O(n) time, O(h) space.

▶ Second Minimum Node In a Binary Tree

In a tree where each node's value is the minimum of its children, find the second-smallest value overall. Return the smallest value strictly greater than the root's, pruning branches that cannot improve.
Pattern: targeted search with pruning. Target: O(n) time, O(h) space.

▶ Smallest Subtree with all the Deepest Nodes

Find the smallest subtree containing every deepest node. Return (depth, node); when both children report equal depth, the current node is the covering one.
Pattern: tuple return, tie means "here". Target: O(n) time, O(h) space.

▶ Largest BST Subtree

Find the largest subtree that is a valid BST. Return (isBST, min, max, size) so a parent decides its own validity from its children's reports alone.
Pattern: composite return type. Target: O(n) time, O(h) space — down from O(n²).

6. Common pitfalls 🚫

• Returning the combined value. The parent must receive a single extendable arm, not the bending answer. Returning L + R + node.val builds invalid paths.
• Forgetting to clamp negatives. In maximum-path problems a negative arm should contribute 0, not drag the total down.
• Not undoing the prefix map in Path Sum III. The single most common bug in this chapter.
• Recomputing to validate. Checking BST-ness with a separate traversal per node is O(n²); return the facts instead.
• Wrong base case. The empty-subtree return must be the identity for your combination — 0 for sums, -inf for maxima, (True, +inf, -inf, 0) for the BST tuple.
• Mutable default arguments for the counts map — a classic Python trap that leaks state between calls.
• Ignoring recursion depth. A skewed tree of 10⁵ nodes exceeds the default limit; mention the iterative option.

7. Key takeaways

1. Two expressions, one visit. contribution goes up, combine goes on the whiteboard.
2. A parent extends one arm, so the return value must describe an arm, never a bend.
3. Richer return types collapse passes. Tuples turn O(n²) verify-and-measure into one traversal.
4. Information can flow downward too — prefix sums on a root-to-node path are just subarray sums.
5. Undo what you recorded before returning to a parent, or siblings see each other's state.
6. Get the base case right. It is the identity element of your combination, not always zero.
7. Why interviewers love it: the code is fifteen lines and the design is everything. Choosing the return type correctly is the answer.

Order: Distribute Coins → Path Sum III → Second Minimum Node → Smallest Subtree with All Deepest Nodes → Largest BST Subtree.

The foundational members of this family — Maximum Path Sum, Diameter, Longest Univalue Path and Max Difference Node–Ancestor — are covered in Coding Interview 101. Work those first; the problems here assume the "return one, score with both" reflex is already automatic.