The idea: a node is solved from its children

In a tree, the subtree under a node splits into the subtrees under its children, and those do not touch each other. So the best answer for a node's subtree can be built from its children's answers. Work from the leaves up to the root, and every node is solved exactly once. This is dynamic programming on a tree, and the standard example is the maximum weight independent set: pick nodes with the largest total weight so that no two picked nodes are joined by an edge.

Node v of weight 5 with children B (in 6, out 7), C (in 2, out 5) and D (in 3, out 6). Take v: 5 + 7 + 5 + 6 = 23, every child out. Skip v: 7 + 5 + 6 = 18, each child takes max of in and out
Taking v forces every child out; skipping v lets each child take its better answer.

Two answers per node

One number per node is not enough. The parent needs to know what its child is worth if the child is taken and if it is not, because taking the parent rules the child out. So each node keeps two:

in(v)  = w(v) + Σ out(c)               (v taken: every child c must be out)
out(v) = Σ max(in(c), out(c))           (v left out: each child is free)
leaf:    in = w,  out = 0
answer = max(in(root), out(root))

In the animation the children's pairs fly up as in | out boxes, and the node writes in (green) and out (blue) under itself. For the sample tree the root A gets in = 23 and out = 18, so the answer is 23 (Demo: sample tree).

Post-order: children before the parent

A node can only be computed when all its children are done. A post-order traversal gives exactly that order: visit the children, then the node. In code it is a plain recursive depth-first search that does the work after the recursive calls return. For the sample tree the order is E F B G C H I J D A, shown as a strip on the right of the canvas.

The sample tree with each node numbered in post-order: E 1, F 2, B 3, G 4, C 5, H 6, I 7, J 8, D 9, A 10, and its in and out values. Root A has in 23, out 18. The chosen nodes A, E, F, G, H, I, J are green
The numbers give the post-order; the green nodes are the best set, worth 23.

Which nodes? Walk back down

The root only gives the total. To find the nodes, go the other way, from the root down (pre-order). The root is free: take it if in > out. A child of a taken node must be out. A child of a node that was left out is free again and makes the same in vs out choice. In the sample tree A is taken (23 > 18), so B, C and D are out, and all six leaves are free and taken.

Why greedy fails

"Take the heaviest node still allowed, then repeat" takes B (6), which blocks A, E and F, then G (5), then D (3), which blocks H, I and J: only 14. The DP finds 23 (Demo: greedy heaviest-first). A heavy node can block several neighbours that are worth more together. The star shows the same thing in its smallest form: the centre weighs 10, but the four leaves of 3 give 12 (Demo: star).

A path is House Robber

If every node has one child, the tree is a path, and the problem is House Robber: never rob two houses next to each other. For 2 7 9 3 1 the DP gives 12 from A, C and E, the same as the one-row table dp[k] = max(dp[k-1], dp[k-2] + v[k]) (Demo: a path is House Robber). The tree version only replaces "the house before" with "the children". With every weight 1 the problem asks for the largest independent set by count: 7 nodes on the sample tree (Demo: all weights 1).

Time and space

MethodTimeSpace
Try every subset of nodesO(2n · n)O(n)
Tree DP, two values per node (this page)O(n)O(n), plus the recursion depth
Same on a general graphNP-hard: there is no "children" order to rely on

Each edge carries one pair from child to parent, so the work is linear. A very deep tree (a long path) can overflow the call stack with recursion; then compute the post-order with an explicit stack, or process nodes from the deepest level up. The same post-order pattern solves many tree problems: subtree sizes, tree diameter and minimum vertex cover, whose weight is the total weight minus the best independent set's.

See also: Memoization vs Tabulation and Top-Down vs Bottom-Up DP for the two ways to order the work, and Optimal Binary Search Tree, where the DP builds a tree instead of running on one.

Stock Trading State Machine DP also keeps several numbers per index, one per state.

What the page leaves out

Rerooting (computing the answer for every possible root in O(n) with a second, top-down pass); trees given as unrooted edge lists, where you pick any root and skip the parent while recursing; other tree DPs such as minimum vertex cover, minimum dominating set, tree diameter and knapsack on a tree; and the iterative version with an explicit stack.