Tree DP
Dynamic programming needs an order in which every subproblem is solved before the problems that use it, and a tree hands that order over for free: postorder. Solve both children, then combine them into the node. Subtree sums show the shape with one number per node. The maximum independent set, the largest sum of nodes with no two adjacent, shows the real trick: a node cannot know whether it may be taken until its parent decides, so it reports two answers upward, its best if taken and its best if skipped, and the parent chooses. Carrying more than one answer per node is what makes most tree problems a single O(n) pass.
Pick a set of nodes with no two of them adjacent, so that their values add up to as much as possible. Whether a node may be picked depends on a choice its parent has not made yet, so each node reports two answers upward: the best total if it is taken, and the best if it is skipped. Postorder again, and the parent decides.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 7, with their answers.
At 20, which is worth more on its own: taking it or skipping it?
Answer: Take it. Take = the value plus the children's skip answers; skip = the sum of each child's best. Compare 20 with 0.
At 40, which is worth more on its own: taking it or skipping it?
Answer: Take it. Take = the value plus the children's skip answers; skip = the sum of each child's best. Compare 40 with 0.
At 30, which is worth more on its own: taking it or skipping it?
Answer: Skip it. Take = the value plus the children's skip answers; skip = the sum of each child's best. Compare 30 with 60.
At 60, which is worth more on its own: taking it or skipping it?
Answer: Take it. Take = the value plus the children's skip answers; skip = the sum of each child's best. Compare 60 with 0.
At 80, which is worth more on its own: taking it or skipping it?
Answer: Take it. Take = the value plus the children's skip answers; skip = the sum of each child's best. Compare 80 with 0.
At 70, which is worth more on its own: taking it or skipping it?
Answer: Skip it. Take = the value plus the children's skip answers; skip = the sum of each child's best. Compare 70 with 140.
At 50, which is worth more on its own: taking it or skipping it?
Answer: Take it. Take = the value plus the children's skip answers; skip = the sum of each child's best. Compare 250 with 200.
How it runs, step by step
Pick a set of nodes with no two of them adjacent, so that their values add up to as much as possible. Whether a node may be picked depends on a choice its parent has not made yet, so each node reports two answers upward: the best total if it is taken, and the best if it is skipped. Postorder again, and the parent decides.
Maximum independent set on a tree of 7 nodes.
20 is a leaf. Taken, it is worth 20; skipped, 0. Both go up, because the parent will decide which one it can use.
At 20: take 20, skip 0.
40 is a leaf. Taken, it is worth 40; skipped, 0. Both go up, because the parent will decide which one it can use.
At 40: take 40, skip 0.
At 30: taking it forbids its children, so take = 30 + 0 + 0 = 30, using the children's skip answers. Skipping it frees each child to use its better answer: skip = 20 + 40 = 60. Skipping wins here, but the parent still gets both.
At 30: take 30, skip 60.
60 is a leaf. Taken, it is worth 60; skipped, 0. Both go up, because the parent will decide which one it can use.
At 60: take 60, skip 0.
80 is a leaf. Taken, it is worth 80; skipped, 0. Both go up, because the parent will decide which one it can use.
At 80: take 80, skip 0.
At 70: taking it forbids its children, so take = 70 + 0 + 0 = 70, using the children's skip answers. Skipping it frees each child to use its better answer: skip = 60 + 80 = 140. Skipping wins here, but the parent still gets both.
At 70: take 70, skip 140.
At 50: taking it forbids its children, so take = 50 + 60 + 140 = 250, using the children's skip answers. Skipping it frees each child to use its better answer: skip = 60 + 140 = 200. Taking wins here, but the parent still gets both.
At 50: take 250, skip 200.
At the root the two answers are take 250 and skip 200, so the best independent set is worth 250: 50, 20, 40, 60, 80. No two of those nodes touch. Every node was visited once and did constant work, O(n), and the only idea beyond plain postorder was carrying two answers instead of one.
Best independent set is worth 250.
Remember
- Postorder is the DP order on a tree: children first, then combine at the node.
- When the parent's choice constrains the child, report both answers upward: taken and skipped.
- Take = value + children's skip answers; skip = sum of each child's better answer.
Topics covered
Where this is used
SecurityMerkle trees in Git and Certificate Transparency
A Merkle tree is the subtree sum with hashing in place of addition: a node's hash is computed from its children's hashes, so nothing can be named until its subtree is finished. One value per node then stands for everything below it. That is why git can diff two commits while skipping any directory whose tree hash matches, and why a Certificate Transparency log can prove that one entry belongs to a log of millions using a path of hashes instead of the whole log.
CompilersRegister allocation for expression trees
The Sethi-Ullman algorithm labels every node of an expression tree with the number of registers needed to evaluate it, derived from the two children's labels: equal labels cost one more register, otherwise the larger one wins. The parent cannot pick an evaluation order until both children have reported, and emitting the heavier subtree first is what keeps the register count minimal. It is the same postorder combine with a register count travelling up instead of a sum.
DatabasesPostgreSQL join planning
The planner builds a plan bottom up and deliberately keeps more than one path per relation: the cheapest one, and also a costlier one that happens to produce rows in a useful sort order. It keeps both for the reason a node here reports take and skip, because the parent, a merge join higher in the plan tree, may prefer the expensive child since it removes a sort. Collapsing each subplan to a single best cost too early throws away the plans that only pay off further up.
BioinformaticsPhylogenetic likelihood
Felsenstein's pruning algorithm scores an evolutionary tree by computing at each internal node a small vector of conditional likelihoods, one per possible DNA base, from its two children's vectors. A single number per node would not work, because the parent's likelihood depends on which base the child held. RAxML and IQ-TREE spend most of their running time inside exactly this postorder combine.
Why it works this way
Where is the memo table?
Most dynamic programming needs a cache because the same subproblem is reached from several places. On a tree every node has exactly one parent, so best(v) is called once and its return value is the table entry: the postorder recursion is the tabulation. If you find yourself wanting a map keyed by node, the input is not a tree: give any node a second parent and the recursion becomes a walk over a DAG that reaches that node twice, which is where real memoization starts to earn its place.
Greedy on the biggest values is wrong
Take a node worth 5 with two children worth 3 each. Greedy grabs the 5 and stops at 5, while taking both children gives 6. A node's own value says nothing about how much value it blocks, and only comparing take against skip once the children are already solved can weigh the two against each other.
The DP returns a number, not the set of nodes
best(root) hands back two totals and you report the larger, but nothing in it records which nodes were chosen. Keep both answers at every node on the way up, then walk back down from the root carrying one flag: a node whose parent was taken must use its skip answer, and any node currently using its take answer is in the set. That is one extra top down pass and the whole thing is still O(n).
The root's answer is not every node's answer
Every value computed here is measured inside a subtree, so best(v) knows nothing about the tree above v. A question that wants a number at every node, such as the total distance from each node to all the others, looks like n separate runs, which is O(n squared). The fix is a second downward pass that hands each child the answer for everything outside its own subtree, which the parent can build from its own answer once that child's subtree is discounted. That is rerooting, and it keeps the cost at O(n).
Read more
- DP on trees, introductionUSACO Guide
- DP on trees, solving for all rootsUSACO Guide
- Independent setWikipedia
- Sethi-Ullman algorithmWikipedia
- Tree MatchingCSES 1130 · cses.fi