Tree Dynamic Programming Interview Patterns
Tree DP combines tree traversal with dynamic programming. The key insight: the answer for a subtree depends only on answers from its children, enabling bottom-up computation via post-order DFS. These patterns appear in “diameter,” “path sum,” and “robber” style problems on trees.
Core Tree DP Template
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def solve(root):
result = [0] # use list to allow mutation in nested function
def dfs(node):
# Base case
if not node:
return 0 # or appropriate base value
# Recurse on children first (post-order)
left_val = dfs(node.left)
right_val = dfs(node.right)
# Compute local answer using children's values
local_answer = ... # problem-specific
# Update global result if needed
result[0] = max(result[0], local_answer)
# Return value that helps the parent
return ... # problem-specific return value
dfs(root)
return result[0]
Pattern 1: Diameter of Binary Tree
The diameter through a node = left_depth + right_depth. The function returns depth for the parent.
def diameter_of_binary_tree(root):
diameter = [0]
def depth(node):
if not node:
return 0
left = depth(node.left)
right = depth(node.right)
diameter[0] = max(diameter[0], left + right)
return 1 + max(left, right)
depth(root)
return diameter[0]
Pattern 2: Maximum Path Sum
Path can start and end at any node. A negative child is excluded (take max with 0).
def max_path_sum(root):
max_sum = [float('-inf')]
def gain(node):
if not node:
return 0
left = max(gain(node.left), 0) # only take positive contributions
right = max(gain(node.right), 0)
# Path through this node (can't use both sides when returning to parent)
max_sum[0] = max(max_sum[0], node.val + left + right)
return node.val + max(left, right) # return best single branch
gain(root)
return max_sum[0]
Pattern 3: House Robber III (Cannot Rob Adjacent Nodes)
Return a pair (rob, skip) for each subtree: max if we rob this node vs. skip it.
def rob(root):
def dfs(node):
if not node:
return (0, 0) # (rob, skip)
left_rob, left_skip = dfs(node.left)
right_rob, right_skip = dfs(node.right)
rob_cur = node.val + left_skip + right_skip
skip_cur = max(left_rob, left_skip) + max(right_rob, right_skip)
return (rob_cur, skip_cur)
return max(dfs(root))
Pattern 4: Longest Univalue Path
Longest path where all nodes have the same value. The function returns the longest arm (not full path) for the parent.
def longest_univalue_path(root):
longest = [0]
def dfs(node):
if not node:
return 0
left = dfs(node.left)
right = dfs(node.right)
left_path = (left + 1) if node.left and node.left.val == node.val else 0
right_path = (right + 1) if node.right and node.right.val == node.val else 0
longest[0] = max(longest[0], left_path + right_path)
return max(left_path, right_path)
dfs(root)
return longest[0]
Pattern 5: Binary Tree Cameras
Minimum cameras to monitor every node. Return state: 0=uncovered, 1=has camera, 2=covered.
def min_camera_cover(root):
cameras = [0]
def dfs(node):
if not node:
return 2 # null nodes are considered covered
left = dfs(node.left)
right = dfs(node.right)
if left == 0 or right == 0:
cameras[0] += 1
return 1 # place camera here
if left == 1 or right == 1:
return 2 # covered by child camera
return 0 # uncovered, let parent decide
if dfs(root) == 0:
cameras[0] += 1
return cameras[0]
Classic Tree DP Problems
| Problem | Return from DFS | Global Update |
|---|---|---|
| Diameter of Binary Tree | Depth (max branch length) | Max left+right depth |
| Maximum Path Sum | Best single branch gain | Max node+left+right |
| House Robber III | (rob_val, skip_val) pair | max(rob, skip) at root |
| Longest Univalue Path | Longest matching arm | Max left_arm+right_arm |
| Binary Tree Cameras | State (0/1/2) | Camera count |
| Sum of Distances in Tree | Subtree size + sum | Re-root DP in O(n) |
| Distribute Coins in Tree | Excess coins (can be negative) | Sum of |excess| moves |
Interview Tips
- Recognize tree DP: “maximum/minimum over all paths,” “can’t use adjacent nodes,” “count something per subtree”
- The DFS return value helps the parent; the global variable tracks the final answer
- When the path through a node contributes to the global answer but you return only the best single branch to the parent — this is the most common tree DP pattern
- Draw the recursion tree on 3-5 nodes before coding; it reveals what to return and what to update