Tree DP
Compute each node's value from its children's values in postorder.
Decision · step 2 of 9Tree DP: Pick nodes, none adjacent, maximise the sum
20 is a leaf. Taken, it is worth 20; skipped, 0. Both go up, because the parent will decide which one it can use.
What you will see
Values bubble up from leaves; each node combines its children.
Cost
| Best | O(n) |
|---|---|
| Average | O(n) |
| Worst | O(n) |
| Space | O(h) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next.
Screen readers: Table cells announce their state and value; each step announces which cells were read and the value written.
Reduced motion: Dependency arrows appear statically and the cell value crossfades.