Chapter 6: Tree DP

Trees are a natural home for dynamic programming. Unlike arrays where you fill left-to-right, trees have a hierarchy: each node's answer depends on its children. The natural fill order is post-order traversal — visit left subtree, visit right subtree, then process the current node. This is bottom-up DP on a tree, and it is often the cleanest way to solve problems on binary trees.

The mental model: replace “table indices” with tree nodes, and replace “fill order” with post-order. At each node you define a small state (one or two values), compute it from children, and return something to the parent. No explicit table is required — the recursion stack carries the subproblem results.

Binary Tree Maximum Path Sum

LeetCode 124: Find the maximum path sum in a binary tree. A path is any connected sequence of nodes where each step goes to a parent or child. The path need not pass through the root.

At each node, track two quantities:

  • Max path through this node — the best path that uses this node as a “bridge” connecting left and right subtrees (does not extend to the parent).
  • Max path ending here going up — the best path starting at this node and going down into one subtree (can be extended by the parent).

The key insight at each node: you choose to extend a path from a child or start fresh at the current node. Negative contributions from children are discarded with max(0, childUp). The global answer is updated whenever a through-path beats the current best.

At node with value v, after processing children:

  up   = max(v, v + leftUp, v + rightUp)     // extend or start fresh
  through = v + max(0, leftUp) + max(0, rightUp)  // bridge left & right
  globalMax = max(globalMax, through)

Post-order DFS returns up to the parent.
Loading...

House Robber III

LeetCode 337: Each node has a value (loot). You cannot rob two directly connected nodes. Maximize total loot. This is the canonical tree DP problem because the decision at each node is binary and cleanly separable from subtrees.

For each node, compute two values:

  • rob[u] — max loot if you rob node u
  • skip[u] — max loot if you skip node u
rob[u]  = val[u] + skip[left] + skip[right]
skip[u] = max(rob[left], skip[left]) + max(rob[right], skip[right])

Answer = max(rob[root], skip[root])

What two values do we compute for each node in House Robber III?

rob
skip
n0=3
n1=2
n2=3
n3=·
n4=3
3
0
n5=·
n6=1
1
0

rob[n1] = 2 + skip[L] + skip[R] = 2 + 0 + 0 = 2

Step 1 / 6
Loading...

Re-Rooting Technique

Standard tree DP usually computes an answer with a fixed root. But some problems ask for the answer when every node is considered as root — for example, “maximum sum of distances from each node to all others.” Re-rooting solves this in O(n) after an initial O(n) DFS.

The idea in three steps:

  1. Root the tree at node 0 and run tree DP to compute subtree answers (e.g., total distance sum for root 0).
  2. Observe how the answer changes when you move the root from parent u to child v — typically a formula using subtree sizes, not a full recomputation.
  3. DFS again from the root, propagating the adjusted answer to every child in O(1) per edge.

When to use re-rooting: The brute-force approach runs tree DP from every node as root — O(n²). If moving the root across an edge has a predictable O(1) update formula, re-rooting cuts this to O(n). Look for problems where the answer depends on which node is the “center.”

Tree DP is just regular DP where the “table indices” are tree nodes and the “fill order” is post-order traversal. You rarely need an explicit table — a DFS that returns a tuple of states from each subtree is enough. Master post-order thinking and most tree DP problems become straightforward.

Summary

  • Fill order: post-order (children before parent)
  • State: typically 1–2 values per node returned to parent
  • Pattern: rob/skip, extend/restart, through/up
  • Re-rooting: O(n) all-root answers after initial DFS