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.
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “What is the rerooting technique and when is it needed?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Standard tree DP (bottom-up) computes the optimal value for each node considering only its subtree — the nodes below it. But some problems ask for the optimal path or value that can go through the node in any direction, including up through the parent. For example: “find the farthest node from each node in the tree.” A naive approach re-roots the tree at each node and runs DFS — O(n^2). Rerooting (also called re-rooting DP or two-pass DP) solves this in O(n): Pass 1 (bottom-up): for each node, compute the longest path going downward into its subtree. Pass 2 (top-down): for each node, compute the longest path going upward through the parent. The up-direction value for a child = 1 + max(up_value of parent, longest_downward_path of parent ignoring this child’s subtree). The answer for each node = max(down_value, up_value). The tricky part of pass 2: when passing down to a child, the “longest path of parent ignoring this child” requires knowing the top-2 longest paths among all children (so when the longest came from the current child, we use the second-longest).”
}
},
{
“@type”: “Question”,
“name”: “How do you solve House Robber III (LC 337) on a binary tree?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “LC 337: cannot rob a node and its direct child on the same path. Standard DP on tree with include/exclude state. For each node, return a pair (rob_this, skip_this): rob_this = node.val + left_skip + right_skip (if we rob this node, children must be skipped). skip_this = max(left_rob, left_skip) + max(right_rob, right_skip) (if we skip this node, each child can be robbed or not independently). Base case (null node): return (0, 0). Answer: max(rob_root, skip_root). This is O(n) time, O(h) space. Common mistake: trying to memoize on node — the include/exclude pairs already encode everything needed, so no additional memoization is necessary. The key insight: the include/exclude pair is the minimal state that captures the constraint (no adjacent nodes robbed) without needing to know anything about ancestors during the bottom-up pass.”
}
},
{
“@type”: “Question”,
“name”: “How do you find the diameter of a tree that is not a binary tree (n-ary tree)?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Diameter = longest path between any two nodes. Generalize the binary tree approach: at each node, consider all children. The two longest depths among children determine the longest path through this node. Algorithm: for each node, compute depth for each child via DFS. Track the top two depths (max1 and max2). Diameter through this node = max1 + max2. Update global max. Return max1 + 1 to the parent (the depth of the subtree rooted here). Implementation: sort children depths in descending order; take the top two. If a node has only one child: the path through it has length = child_depth + 0 (can’t form a two-sided path). The key difference from binary tree: instead of left and right depths, you iterate over all child depths and find the two largest. Time: O(n), space: O(n) for the depth storage during DFS + O(h) recursion stack. Special case: if the tree has 0 or 1 nodes, diameter is 0.”
}
},
{
“@type”: “Question”,
“name”: “What is the approach for the binary tree cameras problem (LC 968)?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Greedy with three states per node: NOT_COVERED (no camera here, not covered by a child), COVERED (covered by a child’s camera but no camera here), HAS_CAMERA (camera placed here). Post-order DFS — determine the state of children before deciding the current node’s state. Rules: (1) If any child is NOT_COVERED: place a camera here (HAS_CAMERA), increment count. (2) Else if any child HAS_CAMERA: this node is COVERED (the child’s camera covers it). (3) Else (all children are COVERED): return NOT_COVERED — parent must handle this node. Special case: if the root is NOT_COVERED after the DFS: increment count (place a camera at the root). Why greedy works: placing cameras as high as possible (at parents of leaves) maximizes each camera’s coverage — a camera covers its parent, itself, and its children. Placing a camera at a leaf covers only the leaf and its parent — wasteful.”
}
},
{
“@type”: “Question”,
“name”: “How does tree DP differ from general graph DP?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Trees are acyclic: this guarantees a natural topological ordering (bottom-up from leaves to root), so there’s no circular dependency between DP states. General graphs may have cycles, requiring cycle detection, Bellman-Ford iterations, or Floyd-Warshall for all-pairs problems. On trees: O(n) time for most DP problems because each edge is traversed at most twice (once down, once up in rerooting). On general graphs: even simple shortest path is O(E log V) with Dijkstra or O(VE) with Bellman-Ford. Trees have at most n-1 edges; general graphs can have O(n^2) edges. Subproblem structure: on trees, the subtree rooted at each node is an independent subproblem (children don’t share state). On general graphs, subproblems can share nodes, requiring more careful state definition (often adding a “visited” bitmask for small n — DP on subsets). Practical interview implication: if the problem input is a tree, immediately think tree DP (O(n) solution is usually possible). If it’s a general graph, complexity will be higher.”
}
}
]
}
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: Coinbase Interview Guide
Asked at: LinkedIn Interview Guide