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
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “What is the general template for tree dynamic programming?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Tree DP uses post-order DFS: recurse on children first, then compute the current node's value using children's results. The DFS function returns a value that helps the parent (e.g., subtree depth, max gain as a branch), while a global variable (or mutable list) tracks the overall answer (e.g., max diameter, max path sum). The key distinction: the return value optimizes the parent's computation; the global variable captures answers that pass through the current node.” }
},
{
“@type”: “Question”,
“name”: “How does the Maximum Path Sum problem differ from the Diameter problem?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “In Diameter, nodes have no values—you count edges or nodes and return depth (positive integer). In Maximum Path Sum, each node has a value that can be negative—you take max(gain, 0) to exclude negative branches. Both use the same structural pattern: the global answer is updated with left+right contributions through the current node, but the function only returns the best single-branch contribution to the parent (not both branches, since a path can't fork).” }
},
{
“@type”: “Question”,
“name”: “How does the House Robber III (tree version) differ from the 1D house robber?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “In 1D House Robber, you use a DP array with two states. In Tree House Robber III, you return a pair (rob_this_node, skip_this_node) from each DFS call. rob_this_node = node.val + left_skip + right_skip (can't rob adjacent children). skip_this_node = max(left_rob, left_skip) + max(right_rob, right_skip) (children can be robbed or skipped independently). The final answer is max(rob_root, skip_root).” }
}
]
}