Graph Theory37 sections · 1633 units
Open in Course

Concept - Tree Dynamic Programming

The Pattern

The Max Depth problem introduced you to Tree DP. The pattern is always the same:

1.1. Define what you want to compute for each node.

2.2. Express it in terms of the answers for the children.

3.3. Write a recursive function that combines child results.

Tree DP is bottom-up: you solve for leaves first, then combine results as you return up the tree. Many tree problems fit this pattern: subtree sizes, diameters, path sums, and more. Once you see the pattern, you can apply it everywhere.