Unit 5.6 · about 3 h
124 / 324Tree dynamic programming
On trees the dependency graph is the input. One post-order pass gives linear time; the only design work is the per-node state.
- derive
- implement
You can now
- Derive per-node state that carries every choice the parent must reason about.
- Implement post-order helpers that return tuples or split return-vs-global quantities.
- Handle skewed trees within the recursion limit or with an explicit stack.
Covers
- Tree dynamic programming
Study, in this order
3 steps
- Maximum independent set on treesAlgorithms - dynamic programming
Section 3.10 (pp. 120-122): \(\operatorname{MIS}(v)\) recurrence over children and grandchildren, memoization into the tree, post-order evaluation, and the \(\operatorname{MISyes}/\operatorname{MISno}\) mutual recurrence
- Tuple state and the return-vs-global splitDSA Handbook - dynamic programming
Two-state DP: the \((\text{rob}, \text{skip})\) tuple on LC 337; The dual-quantity split, with negative values in play, on LC 124 with the \(\max(\text{child\_gain}, 0)\) clamp
- The linear precursorDSA Handbook - dynamic programming
House robber (LC 198): the take-or-skip prototype that LC 337 lifts onto trees, with the
[2,1,1,2]parity-greedy counterexample
Focus on
- Single-number returns fail House Robber III because the parent needs both worlds. Return \((\text{rob\_this}, \text{skip\_this})\) and let the parent pick per scenario.
- LC 124 returns the straight-down chain but compares the bent path globally. Returning the bent path builds two-bend shapes that are not paths.
- Each node is visited once with \(O(1)\) local work, so time is \(O(n)\). Space is the recursion stack \(O(h)\), which is \(n\) on skewed input.
Reproduce closed-book
rob on level-order [3,2,3,null,3,null,1] = 7 and on [3,4,5,1,3,null,1] = 9. State both level-order inputs and both expected outputs.Traps
- Keeping the default limit of 1000 for deep trees. LC 337 allows \(10^4\) nodes and LC 124 allows \(3 \times 10^4\), so a skewed tree raises
RecursionError; raise the limit once at module top level or use an explicit stack. - Initializing the LC 124 global to 0. All-negative trees then return 0 for an empty path; start at negative infinity so the root comparison fires.
- Recomputing grandchildren per node instead of returning both states. The tuple memoizes both worlds in one pass; without it the recursion revisits subtrees.
Practice
LeetCode 337 - House Robber III
Attempt cold. Check [3,2,3,null,3,null,1] = 7 and [3,4,5,1,3,null,1] = 9, then submit.
Attempt cold: return the \((\text{rob}, \text{skip})\) tuple from the helper. After submitting, read the AlgoMaster House Robber III lesson (https://algomaster.io/learn/dsa/house-robber-iii).
Self-test
-
Write the House Robber III recurrence.
\(\text{rob\_this}(v) = \text{val}(v) + \text{skip}(\text{left}) + \text{skip}(\text{right})\); \(\text{skip\_this}(v) = \max(\text{rob}, \text{skip})\) of each child, summed. Answer \(\max(\text{rob}, \text{skip})\) at the root. -
Why is the empty-subtree identity \((0, 0)\)?
An empty subtree contributes no income and imposes no obligation, so both slots add zero to the parent sums. -
LC 124: which quantity travels up and why?
The straight-down chain \(\text{val} + \max(\text{left\_gain}, \text{right\_gain})\). The parent can only extend a linear chain; a bent path extended further would bend twice. -
How does \(\operatorname{MISyes}/\operatorname{MISno}\) relate to the \((\text{rob}, \text{skip})\) tuple?
It is the same pattern: \(\operatorname{MISyes}(v) = 1 + \sum \operatorname{MISno}(\text{children})\) is \(\text{rob\_this}\), and \(\operatorname{MISno}(v) = \sum \max(\text{yes}, \text{no})\) is \(\text{skip\_this}\).
Completion criterion
Stop when
Both reproduce trees return 7 and 9 from a blank file, and you can state what each helper slot means to its parent.
Mark passed, then open 5.7 Only mark this when you can do it without notes.Leads to
- 5.7 Knapsack, subset and bitmask dynamic programming Trade the tree order for capacity and subset orders.
- 5.8 Recurrence proofs and differential validation Prove the per-node recurrence and test it against brute force.
Comes after
- 2.4 Tree representation and traversalsPost-order aggregation with side state becomes tree dynamic programming.
- 5.5 Grid, path and interval dynamic programmingReplace the grid order with post-order on trees.
Resources for this unit
- DSA Handbook - dynamic programming Study Part 9 in order from state and recurrence through sequence, grid, tree and bitmask families. For every example, close the page and reconstruct the state, transition and evaluation order.
- Algorithms - dynamic programming Use the dynamic-programming chapter to derive states and recurrences from first principles and to separate DP from greedy reasoning and shortest paths.
Also in this section
- AlgoMaster DSA - dynamic programming slice Attempt Coin Change, Longest Common Subsequence and House Robber III cold. Write the state, transition, base case and evaluation order first; compare against brute force on small inputs and reconstruct a witness when available.
- Hypothesis - exhaustive and differential DP tests Generate small valid instances, compare memoized, tabulated and exhaustive results, and retain shrunk failures for wrong state, base case, order and compression defects.
- NeetCode - unseen mixed problems Use two tag-hidden mixed problems as the final transfer test. One must require rejecting a tempting greedy or insufficient-state solution with a counterexample.
- Python sys: recursion limit Read
sys.getrecursionlimitandsys.setrecursionlimit: the limit guards the C stack and its safe maximum is platform-dependent. Check the default withgetrecursionlimit(1000 on CPython 3.13), raise it once for memoized DP, or switch to tabulation for deep inputs. - Erickson lecture note D - Advanced Dynamic Programming Read Section D.1 (Saving Space: Divide and Conquer) for the Hirschberg Half-table split that recovers an optimal edit sequence in \(O(m + n)\) space.
- Erickson lecture note J - Approximation Algorithms Read Section J.1 (Load Balancing) for the Partition reduction that makes exact scheduling NP-hard, the
GreedyLoadBalanceheuristic, and Theorem J.1 with its factor-2 proof.