DP on Trees Overview
Tree DP solves optimization problems where the answer for each node depends on the answers for its children. The key insight: trees have no cycles, so there is a natural bottom-up order — process leaves first, then propagate results toward the root. Standard template: DFS post-order traversal. At each node, compute dp[node] using dp[child] values after all children are processed. The DP state for each node might represent: maximum path length in the subtree, total number of nodes, maximum sum, minimum cost. Because each node is visited once, tree DP is O(n) time and O(n) space (for the dp array, plus O(h) recursion stack).
Pattern 1: Subtree Aggregation
The DP value for a node is computed from its children’s values. Examples: tree diameter (LC 543), maximum path sum (LC 124), count of nodes in subtree. For the diameter problem: diameter(node) = left_depth + right_depth. But the function returns max_depth for the parent. Two values per node: the “diameter through this node” (combines left and right) and the “depth of this subtree” (returned to parent). This split is common in tree DP: maintain a global variable for the answer, return a different value for parent propagation.
def diameter(root):
max_d = [0]
def dfs(node):
if not node: return 0
left = dfs(node.left)
right = dfs(node.right)
max_d[0] = max(max_d[0], left + right)
return 1 + max(left, right) # return depth to parent
dfs(root)
return max_d[0]Pattern 2: Include/Exclude (House Robber on Tree, LC 337)
Each node has two states: robbed (include) or not robbed (exclude). If a node is robbed, its children cannot be robbed. If a node is not robbed, each child can be robbed or not (take the max). dp[node] returns a pair (rob, skip): rob = node.val + skip[left] + skip[right]. skip = max(rob[left], skip[left]) + max(rob[right], skip[right]).
def rob(root):
def dfs(node):
if not node: return (0, 0) # (rob, skip)
l_rob, l_skip = dfs(node.left)
r_rob, r_skip = dfs(node.right)
rob = node.val + l_skip + r_skip
skip = max(l_rob, l_skip) + max(r_rob, r_skip)
return (rob, skip)
return max(dfs(root))Pattern 3: Longest Path in Tree (Rerooting)
Find the longest path from each node considering all possible paths (not just paths in the subtree). The challenge: from a given node, the longest path might go “up” through the parent. Rerooting DP solves this in two passes: Pass 1 (bottom-up): compute for each node the longest downward path in its subtree. Pass 2 (top-down): recompute for each node the longest path considering the “up” direction via the parent’s other subtrees. For node v with parent u: up_length[v] = 1 + max(up_length[u], longest_in_other_subtree_of_u). This gives O(n) total for what would be O(n^2) with a naive approach (root at each node separately).
Pattern 4: DP on Tree with Constraints (LC 1372, 968)
LC 1372 (Longest ZigZag Path): at each node, track two values: longest zigzag going left from this node, longest zigzag going right from this node. Transition: if we came from the left, the next step should go right (and vice versa). LC 968 (Binary Tree Cameras): greedy with three states per node — COVERED (has camera), HAS_CAMERA (camera here), NOT_COVERED. Use post-order: if any child is NOT_COVERED, place a camera here. If any child HAS_CAMERA, mark this node as COVERED. If all children are COVERED (no cameras), mark as NOT_COVERED (parent should handle). Count cameras placed. The state machine at each node is the DP.
Interview Approach
Step 1: What does the DP state represent at each node? (max value in subtree, number of nodes, min cost). Step 2: What do I return to the parent vs. what do I track globally? (Often different — the “answer through this node” vs “what the parent needs to continue”). Step 3: Base case — what does a null node or leaf return? Step 4: For rerooting problems, identify that a bottom-up pass alone is insufficient and plan the two-pass approach.
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: Coinbase Interview Guide
Asked at: LinkedIn Interview Guide