Tree DP
Overview
Dynamic Programming applied to tree structures, where the state transitions flow from children to parents (or sometimes parents to children).
Trees naturally possess overlapping subproblems and optimal substructure, allowing O(n) solutions to seemingly exponential problems.
Where used: Network routing optimizations, Organizational hierarchy problems
Why it exists
Problem: We need to optimize a value across a tree structure (like max independent set, or min vertex cover), but greedy choices fail because picking a parent node restricts the children.
Naive approach: Exhaustively try all subsets of nodes and check if they are valid, which is O(2^n).
Better idea: Use Dynamic Programming on the tree using DFS. Since trees have no cycles, the subproblem at any node only depends on the subproblems of its immediate children. A node returns multiple states (e.g., 'max value if I am included' and 'max value if I am excluded').
Why learn this
- It merges two major paradigms: Trees and Dynamic Programming.
- It is a common pattern in hard interview questions (like House Robber III).
Mental model
The boss (parent node) asks their employees (children nodes): 'Give me your best score if I join the project, and your best score if I don't.' The boss then makes the optimal local choice.
Tree DP is usually implemented as a Post-Order DFS. We recurse to the leaves, which compute their base cases. As the recursion unwinds, each parent aggregates the optimal answers from its children based on the state transition rules.
Repeated decision: Based on my children's best scores for state X and state Y, what is my best score for state X and state Y?
Deep dive
Tree DP problems almost always ask for the maximum or minimum of something across a tree. Because a tree is a directed acyclic graph where each node is the root of its own subtree, we can define our DP state around a node and its relationship to its parent.
The most common pattern is tracking two states per node: `dp[node][0]` and `dp[node][1]`. For example, in the 'House Robber III' problem where you cannot rob adjacent nodes:
- `dp[node][0]` = maximum money robbed from this subtree if we DO NOT rob the current node.
- `dp[node][1]` = maximum money robbed from this subtree if we DO rob the current node.
To compute these, we do a post-order traversal (process children first). When we are at a node:
- If we rob it, we cannot rob its children. So `dp[node][1] = node.val + dp[left][0] + dp[right][0]`.
- If we don't rob it, its children can either be robbed or not. So `dp[node][0] = max(dp[left][0], dp[left][1]) + max(dp[right][0], dp[right][1])`.
The node then returns these two values to its parent. The time complexity is `O(n)` because we visit each node once, and the space complexity is `O(h)` for the recursion stack.
Key points
- Post-order Traversal: Information flows bottom-up. A parent cannot compute its DP state until its children have computed theirs.
- State passing: Instead of a global memoization table, state is often just returned directly from the recursive DFS function as a tuple or array.
Pattern: Tree DP (Post-order State Machine)
Recognition cues:
- Find max/min value in a binary tree
- Constraint involves adjacent nodes (parent/child)
Failure signals
- The data structure is not a tree.
Engineering examples
Hierarchical Aggregation
Computing the most cost-effective way to distribute resources in a corporate hierarchy.
The corporate structure is a tree, and optimal budget distribution exhibits optimal substructure.
When not to use
- Graphs with cycles: If the graph has cycles, a simple bottom-up DP fails because the dependency graph has loops. You need general graph algorithms or bitmask DP instead.
Common mistakes
- Using a global memoization table unnecessarily: Because a tree has no cycles and only one path to each node, subproblems don't actually overlap across different branches. We don't need a global `HashMap`; returning the states directly to the parent is enough.
- Forgetting that 'not picked' doesn't force children to be 'picked': If a parent is not selected in a max independent set problem, the children *can* be selected, but they don't *have* to be. We must take the max of the child's picked and not-picked states.
Recall questions
- Why is post-order traversal used for bottom-up Tree DP?
- Why do Tree DP functions often return an array or tuple instead of a single integer?
Understanding checks
In a Tree DP problem where we return `[exclude_val, include_val]`, what should a null leaf node return?
`[0, 0]`.
A non-existent node contributes 0 to any sum or max calculation, serving as the base case for the DP.
A student computes the 'exclude' state of a parent as `left_include + right_include`. Why is this suboptimal?
If the parent is excluded, the children *can* be included, but they could also be excluded if that yields a higher value. It should be `max(left_inc, left_exc) + max(right_inc, right_exc)`.
Forgetting to take the max artificially constrains the search space, potentially missing the optimal solution.
Questions & answers
House Robber III
This is the canonical Tree DP problem. Return `[rob_this, skip_this]` for every node.
Approach: Use a helper function that does a post-order DFS and returns a tuple of two integers.
Practice tasks
House Robber III
Given the root of a binary tree, return the maximum amount of money you can rob without robbing two directly-linked nodes.
Continue learning
Previous: Binary tree & traversals
Previous: Optimal substructure