Tree Dynamic Programming

Process nodes postorder and combine selected versus unselected child states for maximum independent set.

Core idea

Root the tree and define a small state for each parent-child constraint. For maximum independent set, one state selects the node and forces children out; the other leaves it out and frees each child.

Read the visualization

Rows follow postorder so child states are ready before their parent. The two columns expose the selected and unselected recurrences and their final root comparison.

	select	not selected
root 4
L 1
R 5
LL 3
LR 6

Root the tree and prepare selected and unselected states for every node.

1function rob(root: Node | null): number {
const dfs = (nd: Node | null): [number, number] => {
  if (!nd) return [0, 0];               //  empty  subtree leaf 0
  const [ls, ln] = dfs(nd.left);        //  postorder:  compute first  child 
  const [rs, rn] = dfs(nd.right);
  const sel = nd.val + ln + rn;         //  select sel:  child sel not sel select 
  const not = Math.max(ls, ln) + Math.max(rs, rn); //  not selected:  child not
  return [sel, not];
};
return Math.max(...dfs(root));          //  root  take best maximum 
11}

tree ( level order)[4, 1, 5, 3, 6]

postorderLL → LR → L → R → root

1 / 10

Complexity and tradeoffs

Time: O(n). Space: O(n). Each edge contributes once to a constant number of states; recursion depth follows tree height.

Invariant: A completed node row is optimal for its entire subtree under each stated choice for that node.

Where it fits

Tree DP solves independent sets, vertex covers, subtree allocation, and many hierarchical selections. The key is choosing a state that makes child subproblems independent.

Algorithm Visualizer

Tree Dynamic Programming

Core idea

Read the visualization

Complexity and tradeoffs

Where it fits