Pattern Guide
DP on Trees
"Postorder + return value = tree DP. Same template solves diameter, max path, subtree counts."
Tree DP combines dynamic programming with postorder DFS. The child subtrees are subproblems. Learn the postorder-return template, rerooting technique, and how diameter, max path sum, and subtree problems all share the same skeleton.
18 min readtree problems →
Problems you can solve with this pattern
9 problems · click any to start solving
Tree DP — the universal template
// Template: DFS returns the "best single-branch contribution" from this subtree
// Global variable tracks the answer that goes THROUGH any node (uses both children)
let globalAns = -Infinity;
function dfs(node) {
if (!node) return 0; // base case: null contributes 0
const leftVal = dfs(node.left); // best from left subtree
const rightVal = dfs(node.right); // best from right subtree
// === Update global answer (path going through this node) ===
// This path can use BOTH left and right — the "bridge" at this node
globalAns = Math.max(globalAns, leftVal + node.val + rightVal);
// === Return to parent: only ONE branch (left OR right, not both) ===
return node.val + Math.max(leftVal, rightVal);
}
// For diameter (length, not sum):
// leftVal = depth of left subtree, rightVal = depth of right subtree
// globalAns = max(leftVal + rightVal) — longest path through this node
// return 1 + max(leftVal, rightVal) — depth including this nodeTree DP is the natural marriage of DFS and dynamic programming. The key insight: after processing all children of a node, you have exactly the information you need to compute the node's own answer. This is postorder DFS. The hard part is figuring out what each recursive call should return.
Tree DP framework:
1. Identify what each recursive call should RETURN (usually: best value in subtree rooted at this node)
2. Identify what GLOBAL state to update (often: best answer that goes THROUGH this node = left + node + right)
3. The return value goes UP to parent. The global update captures paths that use this node as the "turning point".
Key distinction: return value (goes up, must be a single branch) vs global update (can be the full path through this node).
1. Identify what each recursive call should RETURN (usually: best value in subtree rooted at this node)
2. Identify what GLOBAL state to update (often: best answer that goes THROUGH this node = left + node + right)
3. The return value goes UP to parent. The global update captures paths that use this node as the "turning point".
Key distinction: return value (goes up, must be a single branch) vs global update (can be the full path through this node).
Template — Postorder Return
Tree DP — the universal template
// Template: DFS returns the "best single-branch contribution" from this subtree
// Global variable tracks the answer that goes THROUGH any node (uses both children)
let globalAns = -Infinity;
function dfs(node) {
if (!node) return 0; // base case: null contributes 0
const leftVal = dfs(node.left); // best from left subtree
const rightVal = dfs(node.right); // best from right subtree
// === Update global answer (path going through this node) ===
// This path can use BOTH left and right — the "bridge" at this node
globalAns = Math.max(globalAns, leftVal + node.val + rightVal);
// === Return to parent: only ONE branch (left OR right, not both) ===
return node.val + Math.max(leftVal, rightVal);
}
// For diameter (length, not sum):
// leftVal = depth of left subtree, rightVal = depth of right subtree
// globalAns = max(leftVal + rightVal) — longest path through this node
// return 1 + max(leftVal, rightVal) — depth including this nodeRerooting Technique
Rerooting: Sometimes the answer at each node depends on the rest of the tree ABOVE it, not just below. Two-pass DFS:
1. First DFS (bottom-up): compute subtree answers (sizes, sums, depths)
2. Second DFS (top-down): propagate parent's contribution down
Used for: "sum of distances to all nodes", "find the node that minimizes total distance", problems where each node needs FULL tree info.
1. First DFS (bottom-up): compute subtree answers (sizes, sums, depths)
2. Second DFS (top-down): propagate parent's contribution down
Used for: "sum of distances to all nodes", "find the node that minimizes total distance", problems where each node needs FULL tree info.
Rerooting — sum of distances from every node
function sumOfDistancesInTree(n, edges) {
const graph = Array.from({length:n}, ()=>[]);
for(const [u,v] of edges){ graph[u].push(v); graph[v].push(u); }
const count = new Array(n).fill(1); // subtree sizes
const dist = new Array(n).fill(0); // dist[i] = sum of distances from node i in its subtree
// Pass 1: DFS from node 0 (bottom-up)
const dfs1 = (node, parent) => {
for(const nb of graph[node]){
if(nb===parent) continue;
dfs1(nb, node);
count[node] += count[nb];
dist[node] += dist[nb] + count[nb]; // each node in nb's subtree is 1 further
}
};
// Pass 2: Reroot — propagate from parent to children (top-down)
const dfs2 = (node, parent) => {
for(const nb of graph[node]){
if(nb===parent) continue;
// When we reroot from node to nb:
// - nb's subtree (count[nb] nodes) gets 1 closer
// - rest of tree (n - count[nb] nodes) gets 1 further
dist[nb] = dist[node] - count[nb] + (n - count[nb]);
dfs2(nb, node);
}
};
dfs1(0, -1);
dfs2(0, -1);
return dist;
}Tree DP checklist:
- What does the DFS function RETURN? (usually: best value in subtree, reachable from root of subtree via single path)
- What GLOBAL variable tracks the actual answer? (usually: best path using this node as the "bend")
- Do you need info from ABOVE the node? → rerooting (two passes)
- Do you need to make a binary choice at each node? → return a tuple [choice_a, choice_b]
- Standard template: clamp negative contributions to 0 for max-sum problems
Return value patterns:
- Single value (height, sum): just return it
- Two competing choices: return [take_this, skip_this]
- Multiple aggregates: return [sum, count] or {sum, size}
- Flows/excess: return signed excess (positive = has extra, negative = needs more)
- What does the DFS function RETURN? (usually: best value in subtree, reachable from root of subtree via single path)
- What GLOBAL variable tracks the actual answer? (usually: best path using this node as the "bend")
- Do you need info from ABOVE the node? → rerooting (two passes)
- Do you need to make a binary choice at each node? → return a tuple [choice_a, choice_b]
- Standard template: clamp negative contributions to 0 for max-sum problems
Return value patterns:
- Single value (height, sum): just return it
- Two competing choices: return [take_this, skip_this]
- Multiple aggregates: return [sum, count] or {sum, size}
- Flows/excess: return signed excess (positive = has extra, negative = needs more)