DPAlgorithmaka DP on trees, subtree DP, rerooting

Tree DP

State is a node (plus a small flag); each node combines the answers of its children in post-order.

Pattern: Depth-First SearchPractice (3)
Progress

Overview

A rooted tree is already a DAG, so DP on it needs no clever ordering: compute every child before its parent — a post-order Depth-First Search (DFS). The state is dp[v] (often dp[v][flag]) = the best answer for the subtree rooted at v under some condition about v itself: "v is selected / not selected", "path ends at v", "colour of v". The transition aggregates over children: a sum, a max, the two largest values, or a small knapsack merge.

Members: maximum independent set on a tree (House Robber III), tree diameter (largest top1 + top2 of child depths), binary-tree-maximum-path-sum-style problems, minimum vertex cover / dominating set, counting subtrees, subtree sizes and sums, longest path with constraints, and rerooting where a second top-down pass converts "answer for subtree of v" into "answer for the whole tree rooted at v" for every v in O(n) total.

Complexity is O(n · k) for k flag values, i.e. linear. Constraints are typically n ≤ 10^5–2·10^5, which means recursion depth can be a problem (a path-shaped tree is n deep): use an iterative post-order or raise the stack limit.

treepost-orderDFSO(n)rerootingsubtree

Intuition

A mental model before the formal terms.

Every node runs a tiny company and reports to its parent. A report is a fixed-size summary — "best profit if I am hired, best if I am not" — and a parent only needs its children's reports, never their internal details. Reports flow upward once; the root's report is the answer.

For diameter: each node asks "what is the longest chain hanging below me?" (one number) and, while at it, checks whether joining its two longest child chains through itself beats the global best. The global best is the diameter.

How it works

  1. State: dp[v][s] — optimal value for the subtree of v given v's own status s. Choose s to be whatever a parent must know about its child to make its own decision.
  2. Transition: dp[v][s] = f(v, s) + Σ over children c of g(dp[c][*], s), e.g. take[v] = w[v] + Σ skip[c], skip[v] = Σ max(take[c], skip[c]) for maximum independent set.
  3. Base cases: leaves — take[leaf] = w[leaf], skip[leaf] = 0. With the sum-over-children formulation leaves need no special case.
  4. Order: post-order DFS from the root (children first). Iterative version: obtain a DFS order, then process it in reverse. Answer: combine at the root, or a global best updated at every node for path-type problems.
  5. Rerooting (optional): after the bottom-up pass, do a top-down pass passing "the contribution of everything outside v's subtree" from parent to child; this yields per-root answers in O(n).

Why it works

Subtrees of different children are disjoint and interact only through the parent, so given the parent's status the children's choices are independent. Optimal substructure holds and the transition simply sums/maximizes independent optima.

Post-order guarantees every child value is final before the parent reads it; each edge is used O(1) times, hence linear time.

Recognition

How to tell a problem wants this.

  • Input is a tree (n nodes, n−1 edges, connected) or a binary tree, and the question is about selecting nodes, longest paths, subtree aggregates, or "for every node compute…".
  • Constraints like "no two adjacent chosen nodes", "path through the tree", "distance sums from each node".
  • A DFS that returns one or two numbers per node is the natural first attempt.
“connected groups” → Depth-First Search“number of ways” → Dynamic Programming“binary tree” → Tree Traversal

Interactive visualization

Play, step, change the input. ← → and space work too.

No interactive visualization for this topic yet

Related visualizations are linked under Related.

Pseudocode

1# maximum-weight independent set on a tree (House Robber III generalized)
2dfs(v, parent):
3  take = w[v]; skip = 0
4  for c in adj[v] if c != parent:
5    (t, s) = dfs(c, v)
6    take += s               # if v is taken, children must be skipped
7    skip += max(t, s)       # if v is skipped, children are free
8  return (take, skip)
9answer = max(dfs(root, -1))

Implementations

1# Tree DP: the state is a subtree, and a node's answer is a fold over its
2# children's answers. The natural order is post-order, because a node needs
3# every child finished first. Representative example: maximum weight
4# independent set on a tree, plus subtree sizes and the tree diameter.
5 
6 
71 · Two values per node: best with the node taken, and best without
8def rob_tree_rec(children: list[list[int]], weight: list[int], u: int) -> tuple[int, int]:
9    take, skip = weight[u], 0
10    for v in children[u]:
11        ctake, cskip = rob_tree_rec(children, weight, v)
12        take += cskip  # taking u forbids taking any child
13        skip += max(ctake, cskip)  # skipping u frees each child to choose
14    return take, skip
15 
16 
172 · Iterative post-order, so a deep tree cannot hit the recursion limit
18def max_weight_independent_set(children: list[list[int]], weight: list[int], root: int) -> int:
19    n = len(children)
20    take = [0] * n
21    skip = [0] * n
22    stack = [[root, 0]]  # [node, next child index]
23    while stack:
24        f = stack[-1]
25        u, i = f[0], f[1]
26        if i < len(children[u]):
27            f[1] += 1
28            stack.append([children[u][i], 0])
29        else:
303 · Every child is final, so fold them into this node
31            take[u] = weight[u]
32            skip[u] = 0
33            for v in children[u]:
34                take[u] += skip[v]
35                skip[u] += max(take[v], skip[v])
36            stack.pop()
37    return max(take[root], skip[root])
38 
39 
40# Shared helper: pre-order list, whose reverse is a valid post-order
41def pre_order(children: list[list[int]], root: int) -> list[int]:
42    order = []
43    stack = [root]
44    while stack:
45        u = stack.pop()
46        order.append(u)
47        stack.extend(children[u])
48    return order
49 
50 
514 · Subtree sizes: the same post-order fold with a different combiner
52def subtree_sizes(children: list[list[int]], root: int) -> list[int]:
53    size = [1] * len(children)
54    for u in reversed(pre_order(children, root)):
55        for v in children[u]:
56            size[u] += size[v]
57    return size
58 
59 
605 · Diameter: the longest path through each node is its two deepest branches
61def tree_diameter(children: list[list[int]], root: int) -> int:
62    depth = [0] * len(children)
63    best = 0
64    for u in reversed(pre_order(children, root)):
65        d1 = d2 = 0  # two deepest child depths
66        for v in children[u]:
67            d = depth[v] + 1
68            if d > d1:
69                d1, d2 = d, d1
70            elif d > d2:
71                d2 = d
72        depth[u] = d1
73        best = max(best, d1 + d2)
74    return best
Walkthrough
  1. stack.extend(children[u]) pushes all children in one call, which is faster than a loop of append.
  2. for u in reversed(pre_order(children, root)) iterates the fold order without building a second list — reversed() returns an iterator.
  3. d1, d2 = d, d1 updates both deepest depths in one tuple assignment, which is exactly the shift the two-branch update needs.
  4. The iterative independent-set version uses mutable list frames so f[1] += 1 advances the cursor.
  5. take, skip = weight[u], 0 in the recursive version initialises both in one statement.
Complexity (this implementation)
time O(n) · space O(n)

The recursive version hits RecursionError at about 1000 nodes deep, which is why the iterative one is the production form.

Language notes
  • reversed() on a list returns a lazy iterator; list[::-1] would copy.
  • stack.extend(iterable) is a single C-level call and beats a Python loop of append.
  • sys.setrecursionlimit can raise the cap but risks a C-stack segfault; the iterative form is the safe answer.
  • d1, d2 = d, d1 is the tuple-assignment shift — the other three languages need two statements and a temporary ordering.
Common mistakes in this language
  • Using the recursive version on a deep tree and hitting RecursionError.
  • Writing d1 = d then d2 = d1, which sets both to the same value.
  • Using a tuple for the iterative frame and hitting TypeError on the cursor increment.
Language differences that matter here
  • Recursion depth is the practical driver: CPython raises RecursionError near 1000 frames and JS engines near 10000, so the iterative form is mandatory in both; C++ merely overflows silently, which is worse.
  • The two-deepest-children shift is one statement in Python (d1, d2 = d, d1) and needs careful ordering in the other three.
  • Reverse iteration without copying: C++ rbegin()/rend(), Python reversed(), and a backward index loop in JS/TS — reverse() there would mutate.
  • Pushing many children at once is a single call in Python (stack.extend) and a loop everywhere else.

Complexity

Best
—
Average
—
Worst
O(n · k) for k statuses per node (O(n) typically); O(n · K²) for subtree-knapsack merges with the small-to-large bound
Space
O(n) table + O(height) recursion

Rerooting adds a second O(n) pass. Deep trees may need an iterative DFS.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Optimizing or counting over node selections / paths in a tree.
  • "For every node as root" questions — rerooting.
  • Tree-shaped dependency structures in general (expression trees, hierarchies).
Avoid it when
  • The graph has cycles — it is not a tree; DP on general graphs needs DP on DAGs (if acyclic) or a different approach.
  • The query is a simple traversal or aggregate (Breadth-First Search (BFS)/Depth-First Search (DFS) suffice) with no optimization component.
  • The per-node state would be large (a set of chosen descendants) — reformulate; tree DP works because the state is tiny.

Alternatives

Depth-First Search (DFS)DP on DAGsBinary TreeGreedy Algorithms

Common mistakes

  • Revisiting the parent in an undirected adjacency list (forgetting the c != parent check) — infinite recursion.
  • Recursion depth overflow on path-like trees with n = 10^5; use an explicit stack or a reverse-DFS-order loop.
  • For diameter/path problems, returning the path length instead of the "single chain" length to the parent — parents can only extend one arm.
  • Mixing "answer for subtree" with "global answer": path problems need a global best updated at every node.

Interview patterns

  • House Robber III / maximum independent set; minimum vertex cover on a tree.
  • Diameter of a Binary Tree, Binary Tree Maximum Path Sum, Longest Univalue Path.
  • Count nodes / subtree sums; Sum of Distances in Tree (rerooting).
  • Tree colouring / painting with adjacency constraints (dp[v][colour]).
Interview questions on this
Mock interviews

Example problems

Lowest Common Ancestor of a Binary TreemediumBinary Tree Maximum Path SumhardSerialize and Deserialize Binary Treehard