Course contentsShow
← Computer Science
Lesson 943 of 2,87222. Dynamic ProgrammingFree lesson

Tree DP Fundamentals

Understanding how to apply dynamic programming to tree structures using bottom-up and top-down approaches.

Tree DP Fundamentals

You'll learn: How to apply dynamic programming to tree structures by choosing whether to compute solutions bottom-up from leaves or top-down from the root.

Dynamic programming on trees extends the DP concepts you already know to hierarchical data structures. Instead of filling a table with rows and columns, you're computing optimal solutions at each node based on its children (or parent).

The Core Idea

Trees have a natural recursive structure: each subtree is itself a tree. This makes them perfect for DP! You define a state at each node (like "maximum sum ending here" or "number of ways to color this subtree"), then combine children's states to compute the parent's state.

There are two main approaches:

Bottom-Up (Post-order): Start at the leaves and work toward the root. Each node computes its answer after all children have computed theirs. This is like tabulation—you process smaller subproblems first.

Top-Down (Pre-order with Memoization): Start at the root and recurse down, storing results as you go. Each node may need information from its parent. This resembles memoization—you solve on-demand and cache results.

When to Use Which?

  • Use bottom-up when a node's answer depends only on its subtrees (e.g., "maximum path sum in this subtree")
  • Use top-down when a node needs context from ancestors (e.g., "maximum path from root to any leaf through this node")

Sometimes you need both passes: compute something bottom-up, then use that information in a top-down pass to finalize answers.

Key Takeaway: Tree DP leverages the recursive structure of trees by computing states at each node—either from children upward (bottom-up) or from parent downward (top-down), just like choosing between tabulation and memoization in array-based DP.