---
title: Dynamic Programming on Trees
module: Dynamic Programming
moduleNumber: 8
lessonNumber: 7
order: 807
summary: |
  When the subproblems of a dynamic program are _rooted subtrees_, a single
  post-order DFS solves the whole thing in $O(n)$: each node combines the
  already-computed answers of its children. We meet the archetype — maximum-weight
  independent set on a tree — then the "path through a node" pattern behind tree
  diameter and maximum path sum, and finally **rerooting**, which computes a
  per-node answer for _every_ node as root in $O(n)$ with two passes.
topics: [Dynamic Programming]
sources:
  - book: CLRS
    ref: "Ch. 15 — Dynamic Programming"
  - book: Skiena
    ref: "§ — Dynamic Programming on Trees"
  - book: Erickson
    ref: "Ch. — Dynamic Programming (trees)"
practice:
  - title: 'Diameter of Binary Tree'
    slug: diameter-of-binary-tree
    difficulty: Easy
  - title: 'House Robber III'
    slug: house-robber-iii
    difficulty: Medium
  - title: 'Distribute Coins in Binary Tree'
    slug: distribute-coins-in-binary-tree
    difficulty: Medium
  - title: 'Binary Tree Maximum Path Sum'
    slug: binary-tree-maximum-path-sum
    difficulty: Hard
  - title: 'Sum of Distances in Tree'
    slug: sum-of-distances-in-tree
    difficulty: Hard
---

Dynamic programming works whenever a problem decomposes into
**overlapping subproblems** ordered so that each can be solved from smaller ones
already in hand. On a sequence the natural subproblems are prefixes; on an
interval they are subintervals. On a **tree** the natural subproblems are
**rooted subtrees**, and the ordering that makes them solvable is the
_post-order_ traversal, which visits every node only after all of its children.
Root the tree anywhere, define an answer $f(v)$ for the subtree hanging below
each node $v$, and a single [depth-first sweep](/algorithms/graphs/representations-and-traversal) fills the entire table.

The defining feature of these problems is that the recurrence is **local**: the
answer at $v$ depends only on the answers at $v$'s children,

$$
f(v) = \textsf{combine}\parens{\{\, f(c) : c \text{ a child of } v \,\}},
$$

never on grandchildren directly and never on the rest of the tree. Because the
DFS touches each node and each edge exactly once and does $O(1)$ work per child,
the whole computation runs in $\Theta(n)$ time for a tree on $n$ nodes.[^erickson-tree]
The work is in choosing the _state_: what $f(v)$ must remember about the subtree
so that a parent can combine children without re-descending into them. This is
the usual [optimal-substructure](/algorithms/dynamic-programming/principles)
question, specialized to subtrees.

## The archetype: maximum-weight independent set

Let each node $v$ of a tree carry a weight $w_v \ge 0$. An **independent set** is
a set of nodes no two of which are adjacent; we want one of maximum total weight.
On a general graph this is NP-hard, but on a tree dynamic programming solves
it in linear time, the canonical illustration of the whole technique.[^skiena-tree]

The idea is to make the state record _whether $v$ itself is used_, because that
is the one fact a parent needs in order to decide about itself. Define,
for the subtree rooted at $v$, two values:

- $dp[v][0]$, the best independent set of $v$'s subtree in which $v$ is **not**
  taken;
- $dp[v][1]$, the best one in which $v$ **is** taken.

If $v$ is not taken, each child $c$ is free to be taken or not, so we keep the
better of its two options. If $v$ _is_ taken, no child may be taken, so each
child must contribute its $dp[c][0]$:

$$
dp[v][0] = \sum_{c \text{ child of } v} \max\parens{dp[c][0],\, dp[c][1]},
\qquad
dp[v][1] = w_v + \sum_{c \text{ child of } v} dp[c][0].
$$

The base case falls out for free: a leaf has no children, so $dp[v][0] = 0$ and
$dp[v][1] = w_v$. The answer for the whole tree is
$\max\parens{dp[\text{root}][0],\, dp[\text{root}][1]}$. This is
**House Robber III**, where weights are the money in each house and the
adjacency constraint forbids robbing a parent and its child on the same night.

$$
% caption: Post-order combine for max-weight independent set: each node caches
%          $dp[v][0]/dp[v][1]$ (skip $v$ / take $v$); the chosen set (root + its
%          grandchildren) is shaded
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=12mm, inner sep=0, font=\small},
  level distance=24mm, sibling distance=34mm, >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  % clamp the picture box: tikz over-reserves ~78mm of empty depth below the
  % weights label, leaving a phantom band; pin the bounds to the real content
  % (top legend down to just under the weights line) so the figure ends tight.
  \useasboundingbox (-4.4,1.95) rectangle (7.2,-6.05);
  \node[fill=acc!15, draw=acc, very thick] (a) {\texttt{8/10}}
    child {node (b) {\texttt{4/3}}
      child {node[fill=acc!15, draw=acc, very thick] (d) {\texttt{0/3}}}
      child {node[fill=acc!15, draw=acc, very thick] (e) {\texttt{0/1}}}
    }
    child {node (c) {\texttt{1/4}}
      child {node[fill=acc!15, draw=acc, very thick] (f) {\texttt{0/1}}}
    };
  % slot legend, pointed once at the root with a red annotation leader
  \node[draw=none, font=\footnotesize, align=center, text=red!75!black] (slots)
    at (-3.7,1.4) {\texttt{skip} $v$ \texttt{/} \texttt{take} $v$};
  \draw[->, red!75!black, thick] (slots) to[bend right=12] (a.north west);
  % how the root combines its children's cached values
  \node[draw=none, font=\footnotesize, align=left] (combine) at (4.6,0.2)
    {root, \texttt{take} $v$: \texttt{5 + dp[b][0] + dp[c][0]}\\\texttt{= 5 + 4 + 1 = 10}};
  \node[draw=none, font=\footnotesize] at (0,-5.75)
    {weights: root 5, children 3 and 4, leaves 3, 1, 1};
\end{tikzpicture}
$$

```algorithm
caption: $\textsc{MaxIndepSet}(v)$ — returns the pair $(dp[v][0],\, dp[v][1])$
if $v = \text{nil}$ then
  return $(0, 0)$
$take \gets w_v$ // $v$ taken
$skip \gets 0$   // $v$ excluded
for each child $c$ of $v$ do
  $(c_0, c_1) \gets \textsc{MaxIndepSet}(c)$
  $skip \gets skip + \max(c_0, c_1)$ // child free
  $take \gets take + c_0$            // child forbidden
return $(skip, take)$
```

> **Claim.** $dp[v][0]$ and $dp[v][1]$ are the maximum weights of an independent
> set of $v$'s subtree with $v$ excluded and with $v$ included, respectively.

> **Proof.** By induction on subtree size. A leaf has no children, so the only
> sets are $\emptyset$ (weight $0 = dp[v][0]$) and $\{v\}$ (weight $w_v =
> dp[v][1]$), matching the base case. For the step, assume the recursive calls
> return correct pairs for every child $c$. If $v$ is excluded, each child is free
> to be taken or not, so independently choosing the better of $dp[c][0]$ and
> $dp[c][1]$ is optimal and their sum is $dp[v][0]$. If $v$ is included, no child
> may be taken, so each child contributes exactly $dp[c][0]$, and adding $w_v$
> gives $dp[v][1]$. These two cases exhaust the choices for $v$ and combine each
> child's correct sub-answer optimally, so the returned pair is correct for $v$.
> $\qed$

The procedure visits each node once and spends $O(1)$ per child, hence
$\Theta(n)$ total. The state, _taken vs. not taken_, is
the part worth remembering: a single extra bit per node turns an intractable
graph problem into a linear-time tree sweep.[^clrs-dp]

To see the post-order fill in full, take the tree in the figure with root $r$
(weight $5$), children $b$ (weight $3$) and $c$ (weight $4$), then leaves $d, e$
(weights $3, 1$) under $b$ and leaf $f$ (weight $1$) under $c$. Post-order visits
the leaves first, then $b$, then $c$, then $r$. Each row is the pair
$(dp[v][0],\, dp[v][1]) = (\text{skip } v,\ \text{take } v)$:

| node $v$ | $w_v$ | children | $dp[v][0] = \sum \max(dp[c][0], dp[c][1])$ | $dp[v][1] = w_v + \sum dp[c][0]$ |
|:--:|:--:|:--:|:--|:--|
| $d$ | $3$ | — | $0$ | $3$ |
| $e$ | $1$ | — | $0$ | $1$ |
| $f$ | $1$ | — | $0$ | $1$ |
| $b$ | $3$ | $d, e$ | $\max(0,3) + \max(0,1) = 4$ | $3 + 0 + 0 = 3$ |
| $c$ | $4$ | $f$ | $\max(0,1) = 1$ | $4 + 0 = 4$ |
| $r$ | $5$ | $b, c$ | $\max(4,3) + \max(1,4) = 4 + 4 = 8$ | $5 + 4 + 1 = 10$ |

The answer is $\max(dp[r][0], dp[r][1]) = \max(8, 10) = 10$, achieved by
_taking_ $r$. Taking $r$ forbids $b$ and $c$, so we descend into $dp[b][0]$ and
$dp[c][0]$, each of which _skips_ its own node and is free to take the leaves
below: that selects $r$, $d$, $e$, $f$, with weights $5 + 3 + 1 + 1 = 10$ — the
shaded set in the figure. Every value in the table is read from children already
computed, never recomputed — that single-pass reuse is what makes the sweep linear.

::impl{algo="tree_max_independent_set"}

## Paths through a node: diameter and maximum path sum

A second pattern arises when the quantity we care about is a **path**, not a set.
The **diameter** of a tree is the number of edges on its longest path; the
**maximum path sum** (where nodes carry values, possibly negative) is the largest
total along any path. Neither is a clean subtree quantity, because the optimal
path may _bend_ at some node, descending into two different children.

The resolution is the signature move of tree DP on paths. At each node $v$,
let $\textsf{down}(v)$ be the best _downward_ path that starts at $v$ and goes
into a single subtree. A child $c$ extends to $\textsf{down}(c) + (\text{edge or }
w_v)$. The best path that **bends at $v$** combines its two best children:

$$
\textsf{best}(v) = \textsf{down}(c_1) + \textsf{down}(c_2) \;(+\, w_v),
$$

for the two children with the largest downward values. The distinction below is
the source of the classic bug:

> **Remark (Return one thing, update another).** A node _returns_ to its parent only the
> single best downward extension $\textsf{down}(v)$, a path the parent can lengthen.
> But it _updates_ a global maximum with the bent path $\textsf{best}(v)$, which
> uses **two** children and therefore can **not** be extended upward. Mixing the
> two, returning the two-child sum to the parent, would let a path fork twice
> and is the classic bug.

```algorithm
caption: $\textsc{MaxPathSum}(v)$ — returns best downward path; updates global $ans$
if $v = \text{nil}$ then
  return $0$
$L \gets \max(0, \textsc{MaxPathSum}(left(v)))$  // drop negative branches
$R \gets \max(0, \textsc{MaxPathSum}(right(v)))$
$ans \gets \max(ans,\; w_v + L + R)$             // bend here: both sides
return $w_v + \max(L, R)$                         // extendable: one side
```

$$
% caption: Max path sum: node $20$ bends, combining both children for
%          $\textsf{best}=15+20+7=42$ (global max), but returns only
%          $\textsf{down}=20+15=35$ upward
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=9mm, inner sep=0, font=\small},
  level distance=15mm, sibling distance=24mm, >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \node (r) {\texttt{-10}}
    child {node (l) {$9$}}
    child {node[draw=acc, very thick, text=acc] (m) {$20$}
      child {node (a) {$15$}}
      child {node (b) {$7$}}
    };
  \draw[->, acc, thick] (a) to[bend left=12] (m);
  \draw[->, acc, thick] (b) to[bend right=12] (m);
  \node[draw=none, font=\footnotesize, text=acc, align=left] at (5.0,-1.5)
    {bend at 20:\\\texttt{best = 15 + 20 + 7 = 42}};
  \node[draw=none, font=\footnotesize, align=left] at (5.0,-3.2)
    {return up:\\\texttt{down = 20 + 15 = 35}};
\end{tikzpicture}
$$

For **Binary Tree Maximum Path Sum** the $\max(0, \cdot)$ prunes branches that
would only hurt the total; the global $ans$ records the best bend seen anywhere.
On the tree in the figure — root $-10$ with left leaf $9$ and right child $20$
whose children are leaves $15$ and $7$ — the post-order pass runs as follows. The
leaves $9$, $15$, $7$ each return their own value (no children), and update $ans$
with themselves. At node $20$: $L = \max(0, 15) = 15$, $R = \max(0, 7) = 7$, so
the bent path is $20 + 15 + 7 = 42$, which becomes the new $ans$; it returns
upward only $20 + \max(15, 7) = 35$. At the root $-10$: $L = \max(0, 9) = 9$,
$R = \max(0, 35) = 35$, and its bent path is $-10 + 9 + 35 = 34 < 42$, so $ans$
stays $42$. The negative root could not improve the answer, and the $\max(0,
\cdot)$ guards ensured no negative branch was added into a sum. The final
answer is $42$, the two-child bend at $20$ — a path that the node correctly
_updated the global with_ but did _not_ return.

For **Diameter of Binary Tree** the same skeleton applies with edge counts in
place of values: $\textsf{down}(v) = 1 + \max(\textsf{down}(\text{children}))$ and
the diameter is the largest $\textsf{down}(c_1) + \textsf{down}(c_2)$ over all
nodes $v$. Both run in $\Theta(n)$: one post-order pass, $O(1)$ per node.

::impl{algo="binary_tree_max_path_sum,tree_diameter"}

## Rerooting: an answer for _every_ root in $O(n)$

The hardest variant asks for a quantity computed _with each node in turn as the
root_: for every node $v$, say, the sum of distances from $v$ to all
other nodes. Re-running an $O(n)$ DFS from each of the $n$ roots costs $O(n^2)$.
**Rerooting** (also called the "all-roots" or "re-root" technique) computes all
$n$ answers in $O(n)$ total, with two DFS passes: one _down_, one _up_.[^skiena-reroot]

Take **Sum of Distances in Tree**. Fix an arbitrary root $r$ and let $S(v)$ be
the number of nodes in $v$'s subtree and $D(v)$ the sum of distances from $v$ to
every node _inside its own subtree_. A post-order pass computes both, since a
child $c$ at distance $1$ contributes $D(c) + S(c)$ (every node under $c$ is one
edge farther from $v$ than from $c$):

$$
S(v) = 1 + \sum_{c} S(c),
\qquad
D(v) = \sum_{c} \parens{D(c) + S(c)}.
$$

$$
% caption: Down-pass at root $r$: each node caches $S$ (subtree size) and $D$ (in-subtree
%          distance sum); $D(r)=6$ is the true answer only at the root
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=11mm, inner sep=0, font=\footnotesize},
  level distance=16mm, sibling distance=30mm, >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \node[draw=acc, very thick, text=acc] (r) {$r$}
    child {node (a) {$a$}
      child {node (c) {$c$}}
    }
    child {node (b) {$b$}
      child {node (d) {$d$}}
    };
  \node[draw=none, font=\footnotesize, text=acc] at (0,1.0) {\texttt{S=5, D=6}};
  \node[draw=none, font=\footnotesize] at (-2.7,-1.6) {\texttt{S=2, D=1}};
  \node[draw=none, font=\footnotesize] at (2.7,-1.6) {\texttt{S=2, D=1}};
  \node[draw=none, font=\footnotesize] at (-2.7,-3.5) {\texttt{S=1, D=0}};
  \node[draw=none, font=\footnotesize] at (2.7,-3.5) {\texttt{S=1, D=0}};
\end{tikzpicture}
$$

That gives the _true global_ answer only at the root, where the subtree is the
whole tree: $\textsf{ans}(r) = D(r)$. The second pass pushes the answer from a
parent to each child in $O(1)$. Moving the root from $u$ to an adjacent child
$v$, the $S(v)$ nodes on $v$'s side each get **one closer** (distance drops by
$1$) and the remaining $n - S(v)$ nodes each get **one farther**:

$$
\textsf{ans}(v) = \textsf{ans}(u) - S(v) + \parens{n - S(v)}.
$$

Subtract the subtree's contribution, add the rest: the entire adjustment is a
single $O(1)$ formula, so the down-pass plus the up-pass together are $\Theta(n)$.

$$
% caption: Rerooting from parent $u$ to child $v$: subtract $v$'s subtree, add the other
%          $n - S(v)$ nodes
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=9mm, inner sep=0, font=\small},
  >=stealth, level distance=16mm, sibling distance=22mm]
  \definecolor{acc}{HTML}{2348F2}
  \node (u) {$u$}
    child {node[draw=acc, very thick, text=acc] (v) {$v$}
      child {node {}}
      child {node {}}
    }
    child {node (w) {}
      child {node {}}
    };
  % structural reroot move (u -> v): accent; label sits ON its own edge, offset
  % to the left so it is clear of the u--w edge and unambiguously names u->v.
  \draw[->, very thick, draw=acc] (u) to[bend left=22]
    node[draw=none, font=\footnotesize, text=acc, fill=white, inner sep=1.5pt, pos=0.5, left=0.5mm] {reroot} (v);
  \node[draw=none, font=\footnotesize, align=left, text=acc] at (3.8,-1.6)
    {\texttt{ans(v) =}\\\texttt{ans(u) - S(v)}\\\texttt{+ (n - S(v))}};
\end{tikzpicture}
$$

> **Remark (Why two passes suffice).** The down-pass anchors one correct global answer (at
> the root). The up-pass is a second post-order/pre-order DFS that, knowing the
> parent's correct global answer, derives each child's in $O(1)$ by accounting
> only for the nodes that cross the single edge between them. Every edge is
> crossed once in each direction, so the adjustment is computed $2(n-1)$ times in
> all, linear. The pattern generalizes: any quantity whose change across one edge
> can be expressed from cached subtree aggregates ($S$, $D$, counts, sums) can be
> rerooted in $O(n)$.

On the five-node tree above (root $r$ with children $a, b$; then $c$ under $a$ and
$d$ under $b$), the down-pass fixes $\textsf{ans}(r) = D(r) = 6$. The up-pass then
propagates outward, each step a single subtract-add. Moving to $a$: its subtree
has $S(a) = 2$ nodes, so $\textsf{ans}(a) = 6 - 2 + (5 - 2) = 7$. From $a$ to its
child $c$ ($S(c) = 1$): $\textsf{ans}(c) = 7 - 1 + (5 - 1) = 10$. By symmetry
$\textsf{ans}(b) = 7$ and $\textsf{ans}(d) = 10$. Every value matches a direct
BFS from that node, but the whole sweep is linear.

$$
% caption: The up-pass on the five-node tree: the root's answer 6 propagates outward,
%          each edge applying subtract-my-subtree, add-the-rest to land the exact
%          distance sum at every node.
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=10mm, inner sep=0, font=\footnotesize},
  level distance=15mm, sibling distance=30mm, >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \node[fill=acc!15, draw=acc, very thick] (r) {$r$}
    child {node (a) {$a$}
      child {node (c) {$c$}}
    }
    child {node (b) {$b$}
      child {node (d) {$d$}}
    };
  \node[draw=none, font=\footnotesize, text=acc] at (0,1.0) {\texttt{ans=6}};
  \node[draw=none, font=\footnotesize] at (-2.9,-1.5) {\texttt{ans=7}};
  \node[draw=none, font=\footnotesize] at (2.9,-1.5) {\texttt{ans=7}};
  \node[draw=none, font=\footnotesize] at (-2.9,-3.3) {\texttt{ans=10}};
  \node[draw=none, font=\footnotesize] at (2.9,-3.3) {\texttt{ans=10}};
\end{tikzpicture}
$$

A related linear-time tree DP is **Distribute Coins in Binary Tree**: each node
returns to its parent the _net_ coins it must send up or pull down, the signed
excess $\textsf{coins} - 1$ summed over its subtree, and the total number of
moves is the sum of absolute flows along every edge, accumulated in one
post-order pass. Same shape: a local return value, a global accumulator,
$\Theta(n)$ time.

::impl{algo="sum_of_distances_in_tree,distribute_coins"}

## From trees back to hard graphs

Tree DP is a special case of a deeper result. The reason maximum-weight independent
set is linear on trees but NP-hard on general graphs is **treewidth**: a tree has
treewidth $1$, and Courcelle's theorem (Courcelle, 1990) says that _any_ graph
property expressible in monadic second-order logic — independent set, dominating
set, Hamiltonicity, $k$-coloring for fixed $k$ — is decidable in linear time on
graphs of bounded treewidth, by a dynamic program over a **tree decomposition**.
The post-order combine in this lesson is the treewidth-$1$ instance of that DP; on
a width-$w$ decomposition each "bag" of $\le w{+}1$ vertices plays the role a
single node plays here, and the state grows to roughly $2^{w}$ per bag, so the
runtime is $O(2^{w} \cdot n)$. This is why bounded treewidth — the graph is
nearly a tree — is such a useful property of an instance.[^courcelle]

Rerooting, the two-pass "all-roots" technique, is the tree analog of an idea that
recurs across algorithms: compute one anchored answer, then transfer it along edges
with a cheap difference. The same accounting drives the **all-pairs** flavor of many
tree problems and appears in Skiena's treatment of tree DP and in competitive
references under names like "in-and-out DP" or "up-and-down DP". It also connects to
[centroid decomposition](/algorithms/graphs/representations-and-traversal): both
exploit that a tree, unlike a general graph, has a balanced recursive structure that
turns an apparent $O(n^2)$ over all pairs of nodes into $O(n)$ or $O(n \log n)$.

A modern practical descendant is **belief propagation** (Pearl, 1988) on graphical
models: on a tree-structured probabilistic model, the sum-product message-passing
algorithm computes exact marginals in one up-pass and one down-pass — structurally
identical to rerooting, with $\max$/$\sum$ over children replaced by products of
messages. The independent-set recurrence here is the "hard-core model" special case,
and the reason inference is exact on trees but only approximate ("loopy BP") on
general graphs is, again, that trees have no cycles to double-count.

## Takeaways

- On a tree, the natural DP subproblems are **rooted subtrees**, solved by a
  single **post-order DFS** that combines each node's children in $O(1)$, hence
  $\Theta(n)$ overall, since every node and edge is processed once.
- The state must capture just what a parent needs. For **maximum-weight
  independent set** (House Robber III) that is one bit, _taken_ vs. _not taken_:
  $dp[v][0]=\sum_c\max(dp[c][0],dp[c][1])$ and $dp[v][1]=w_v+\sum_c dp[c][0]$.
- The **path-through-a-node** pattern (diameter, max path sum) **returns one
  thing and updates another**: return the single best downward extension to the
  parent, but update a global max with the two-child bent path, never returning the
  bent path.
- **Rerooting** computes a per-root answer for _all_ $n$ nodes in $O(n)$ via two
  passes: a down-pass fixes the root's answer from subtree aggregates, an up-pass
  transfers it edge-by-edge with a "subtract my subtree, add the rest" $O(1)$
  adjustment.
- The recurring design questions are always the same: _what does a node return to
  its parent_, and _what aggregate must the subtree cache_ so the combine stays
  $O(1)$.

[^erickson-tree]: **Erickson**, Ch. — Dynamic Programming (trees): subtree subproblems solved bottom-up by post-order traversal in $O(n)$.
[^skiena-tree]: **Skiena**, § — Dynamic Programming on Trees: maximum independent set on trees as the linear-time archetype of tree DP.
[^clrs-dp]: **CLRS**, Ch. 15 — Dynamic Programming: optimal substructure and the combination of subproblem solutions, instantiated here on rooted subtrees.
[^skiena-reroot]: **Skiena**, § — Dynamic Programming on Trees: the all-roots / rerooting technique computing every node's answer in $O(n)$ with two DFS passes.
[^courcelle]: **Courcelle** (1990), "The monadic second-order logic of graphs I": any MSO-expressible graph property is linear-time decidable on graphs of bounded treewidth via DP over a tree decomposition; tree DP is the treewidth-$1$ case. See also **Pearl** (1988), _Probabilistic Reasoning in Intelligent Systems_, for the sum-product / belief-propagation analog on tree-structured models.