- API Kernel:
TreeDP - Why Tree DP?
- Core Insight
- Universal Template Structure
- State Design Strategies
- State Transition Patterns
- Pattern Variants
- Problem: House Robber III (LC 337)
- Problem: Binary Tree Maximum Path Sum (LC 124)
- Problem: Binary Tree Cameras (LC 968)
- Pattern Comparison
- State Design Summary
- Complexity Comparison
- Return Value vs Global State
- When to Use Tree DP
- Quick Reference Templates
- State Design Cheat Sheet
Core Mechanism: Apply dynamic programming on tree structures by computing states bottom-up (post-order) where each node's state depends on its children's states.
Tree DP solves optimization problems on trees where:
- You need to make decisions at each node (include/exclude, color, etc.)
- The optimal solution depends on subtree solutions
- Simple greedy doesn't work due to dependent choices
Trees have a natural recursive structure. Process children first (post-order DFS), then combine their states to compute the parent's state.
1
/ \
2 3
/ \
4 5
Post-order: 4 → 5 → 2 → 3 → 1
At each node, compute:
dp[node] = f(dp[children], node_value)
def tree_dp(root):
def dfs(node):
if not node:
return base_state
# Process children first (post-order)
left_state = dfs(node.left)
right_state = dfs(node.right)
# Compute current node's state from children
current_state = combine(left_state, right_state, node.val)
return current_state
return extract_answer(dfs(root))| Pattern | State Type | Example |
|---|---|---|
| Include/Exclude | (with_node, without_node) | House Robber III |
| Path Through Node | max_path_ending_here | Max Path Sum |
| Coverage States | (covered, has_camera, not_covered) | Binary Tree Cameras |
| Subtree Info | (height, is_balanced) | Balanced Tree Check |
def dfs(node):
if not node:
return (0, 0) # (with, without)
left = dfs(node.left)
right = dfs(node.right)
# Include current: can't include children
with_current = node.val + left[1] + right[1]
# Exclude current: take max of children
without_current = max(left) + max(right)
return (with_current, without_current)def dfs(node):
nonlocal max_sum
if not node:
return 0
# Max contribution from each child (can't take negative)
left = max(0, dfs(node.left))
right = max(0, dfs(node.right))
# Path through this node
path_sum = node.val + left + right
max_sum = max(max_sum, path_sum)
# Return max single-branch contribution
return node.val + max(left, right)# States: 0=not covered, 1=covered no camera, 2=has camera
def dfs(node):
if not node:
return 1 # null nodes are "covered"
left = dfs(node.left)
right = dfs(node.right)
if left == 0 or right == 0:
return 2 # Must place camera
if left == 2 or right == 2:
return 1 # Covered by child's camera
return 0 # Not covered, needs parent- Binary Choice: Include/exclude node in solution
- Path Optimization: Find optimal path through nodes
- State Machine: Multiple states per node with transitions
- Aggregation: Collect information from entire subtree
Base Template for include/exclude tree DP.
The thief has found a new place for thievery. Houses form a binary tree. If two directly-linked houses are broken into, they will alert the police. Maximize the total amount robbed.
Invariant: For each node, track two states:
- Maximum if we include this node
- Maximum if we exclude this node
Key Insight: If we include parent, we can't include children. If we exclude parent, children are independent.
Tree: 3
/ \
4 5
/ \ \
1 3 1
Post-order computation:
Node 1: include=1, exclude=0
Node 3: include=3, exclude=0
Node 4: include=4+0+0=4, exclude=max(1,0)+max(3,0)=4
Node 5: include=5+0=5, exclude=max(1,0)=1
Node 1: include=1, exclude=0
Node 3: include=3+4+1=8, exclude=max(4,4)+max(5,1)=9
Answer: max(8, 9) = 9 (rob nodes 4, 5, and leaf 3)
def rob(root: TreeNode) -> int:
def dfs(node):
if not node:
return (0, 0) # (include, exclude)
left = dfs(node.left)
right = dfs(node.right)
# Include this node: must exclude children
include = node.val + left[1] + right[1]
# Exclude this node: children are free choice
exclude = max(left) + max(right)
return (include, exclude)
return max(dfs(root)) Parent
/ \
Child Child
Include parent → must exclude both children
Exclude parent → each child can be included or excluded (independent)
- Time: O(n) - visit each node once
- Space: O(h) - recursion stack depth (h = tree height)
The key constraint is "adjacent nodes can't both be selected." With two states per node, we capture all legal combinations:
- Parent included → children must be excluded
- Parent excluded → children independently optimal
Variant: Path optimization tree DP.
A path in a binary tree is a sequence of nodes where each pair of adjacent nodes has an edge. The path sum is the sum of node values. Find the maximum path sum.
Invariant: For each node, track the maximum contribution it can make to a path extending upward.
Key Insight: A path can:
- Go through a node (left → node → right)
- Extend from a node upward (can only use one branch)
Delta from Base: Track global maximum separately from returned value.
Tree: -10
/ \
9 20
/ \
15 7
DFS returns (max contribution upward):
Node 9: return 9, global max = 9
Node 15: return 15, global max = 15
Node 7: return 7, global max = 15
Node 20: path=20+15+7=42, return 20+15=35, global=42
Node -10: path=-10+9+35=34, return max(-10+9,-10+35)=25
Answer: 42 (path 15 → 20 → 7)
def maxPathSum(root: TreeNode) -> int:
max_sum = float('-inf')
def dfs(node):
nonlocal max_sum
if not node:
return 0
# Max contribution from children (ignore negative)
left = max(0, dfs(node.left))
right = max(0, dfs(node.right))
# Path through this node (potential answer)
path_through = node.val + left + right
max_sum = max(max_sum, path_through)
# Return max single-branch contribution
# (path can only extend one way upward)
return node.val + max(left, right)
dfs(root)
return max_sum A
/ \
B C
If we're building a path from A's parent:
- We can go Parent → A → B (one branch)
- We can go Parent → A → C (one branch)
- We CAN'T go B ← A → C then up to Parent (path would branch)
So we return the max single-branch contribution.
| Aspect | House Robber | Max Path Sum |
|---|---|---|
| State | (include, exclude) | single value |
| Return | both states | max contribution upward |
| Answer | max of root states | global max (any node) |
| Negative | keep if positive | clamp to 0 |
- Time: O(n)
- Space: O(h)
- Single node: Answer is node.val
- All negative: Must include at least one node
- Negative children: Clamp contribution to 0 (don't use negative branches)
Advanced Variant: Multi-state tree DP.
You are given the root of a binary tree. Install cameras on tree nodes such that every node is monitored. A camera can monitor its parent, itself, and immediate children. Return the minimum number of cameras needed.
Invariant: Each node is in one of three states:
- State 0: Not covered (needs parent's camera)
- State 1: Covered but no camera here
- State 2: Has camera (covers parent and children)
Delta from Base: Three states with coverage rules.
Tree: 0
/
0
/ \
0 0
Post-order (leaves first):
Leaf nodes: return 0 (not covered)
Parent of leaves: child=0 → must place camera → return 2
Root: child=2 → covered → return 1
Cameras placed: 1 (at the parent of leaves)
def get_state(left, right):
# If any child is not covered, must place camera
if left == 0 or right == 0:
return 2 # Place camera, count += 1
# If any child has camera, this node is covered
if left == 2 or right == 2:
return 1 # Covered, no camera needed
# Both children covered but no camera nearby
return 0 # Not covered, needs parentdef minCameraCover(root: TreeNode) -> int:
cameras = 0
def dfs(node):
nonlocal cameras
if not node:
return 1 # Null is "covered" (don't need camera for it)
left = dfs(node.left)
right = dfs(node.right)
# Rule 1: Child not covered → place camera here
if left == 0 or right == 0:
cameras += 1
return 2
# Rule 2: Child has camera → we're covered
if left == 2 or right == 2:
return 1
# Rule 3: Children covered, no camera nearby
return 0
# Handle root specially
if dfs(root) == 0:
cameras += 1 # Root not covered, needs camera
return camerasThe strategy is leaf-driven:
- Don't place cameras on leaves (wasteful)
- Place cameras on parents of leaves (covers 3 nodes)
- Propagate coverage upward
This greedy approach is optimal because:
- Each camera covers at most 3 levels
- Placing at parents of leaves maximizes coverage
Child States → Parent State
─────────────────────────────────
Any child = 0 → 2 (place camera)
Both covered,
one has camera → 1 (covered)
Both = 1 → 0 (not covered)
- Time: O(n)
- Space: O(h)
Two states (has camera / no camera) aren't enough:
- "No camera" doesn't distinguish "covered by child" vs "needs coverage"
- We need to know if a node NEEDS a camera from its parent
| Aspect | House Robber | Max Path | Cameras |
|---|---|---|---|
| States | 2 | 1 + global | 3 |
| Goal | Maximize sum | Max path | Minimize count |
| Constraint | No adjacent | Path structure | Full coverage |
| Problem | States Per Node | Return Value | Global Tracking |
|---|---|---|---|
| House Robber III | 2 (include, exclude) | Both states | No |
| Max Path Sum | 1 (contribution) | Max branch contribution | Yes (max path) |
| Binary Tree Cameras | 3 (coverage states) | Coverage state | Yes (camera count) |
| Pattern Type | When to Use | State Example |
|---|---|---|
| Include/Exclude | Binary choice per node | (with_node, without_node) |
| Path Contribution | Optimize paths | max_contribution_upward |
| Multi-State | Complex constraints | (not_covered, covered, has_camera) |
| Problem | Time | Space | Key Operation |
|---|---|---|---|
| House Robber III | O(n) | O(h) | Max of combinations |
| Max Path Sum | O(n) | O(h) | Sum with clamping |
| Binary Tree Cameras | O(n) | O(h) | State transition |
| Problem | Return to Parent | Global Update |
|---|---|---|
| House Robber | Both states for parent's choice | None |
| Max Path | Single branch (path constraint) | Max of all paths |
| Cameras | Coverage state | Camera count |
Use tree DP when you see:
- Binary tree structure with optimization requirement
- Node-level decisions that affect neighbors (parent/children)
- Constraint propagation through tree edges
- Optimal substructure where subtree solutions combine for parent
Problem on a tree?
├── No → Not tree DP
└── Yes → What's the constraint?
├── Node selection (include/exclude) → Include/Exclude DP
│ └── Examples: House Robber III, Max Independent Set
├── Path optimization → Path Contribution DP
│ └── Examples: Max Path Sum, Diameter
└── Coverage/coloring → Multi-State DP
└── Examples: Binary Tree Cameras, Vertex Cover
-
What information does a parent need from children?
- Binary choice → 2 states
- Path contribution → 1 value
- Multiple scenarios → 3+ states
-
Is the answer at the root or anywhere?
- At root → return from DFS
- Anywhere → track global max/min
-
Can negative values be ignored?
- Yes → clamp contributions to 0
- No → handle negative cases
| Alternative | When to Prefer |
|---|---|
| BFS/DFS | Just traversal, no optimization |
| Greedy | Local optimal = global optimal |
| 1D DP | Tree degenerates to path |
| Memoization | Same subtree appears multiple times (rare in trees) |
- Forgetting base case: Handle null nodes properly
- Wrong state count: More constraints need more states
- Confusing return vs global: Know what to return vs track globally
- Off-by-one in coverage: Careful with parent/child relationships
def tree_dp_include_exclude(root: TreeNode) -> int:
"""
Returns maximum value with constraint:
adjacent nodes can't both be selected.
"""
def dfs(node):
if not node:
return (0, 0) # (include, exclude)
left = dfs(node.left)
right = dfs(node.right)
# Include: must exclude children
include = node.val + left[1] + right[1]
# Exclude: children are free choice
exclude = max(left) + max(right)
return (include, exclude)
return max(dfs(root))def tree_dp_path_sum(root: TreeNode) -> int:
"""
Find maximum path sum where path can start/end at any node.
"""
max_sum = float('-inf')
def dfs(node):
nonlocal max_sum
if not node:
return 0
# Get max contribution from each branch (clamp negative to 0)
left = max(0, dfs(node.left))
right = max(0, dfs(node.right))
# Path through this node
path_through = node.val + left + right
max_sum = max(max_sum, path_through)
# Return single-branch contribution for parent
return node.val + max(left, right)
dfs(root)
return max_sumdef tree_dp_coverage(root: TreeNode) -> int:
"""
Minimum cameras to cover all nodes.
States: 0=not covered, 1=covered, 2=has camera
"""
cameras = 0
def dfs(node):
nonlocal cameras
if not node:
return 1 # Null is "covered"
left = dfs(node.left)
right = dfs(node.right)
if left == 0 or right == 0:
cameras += 1
return 2 # Place camera
if left == 2 or right == 2:
return 1 # Covered by child
return 0 # Not covered
if dfs(root) == 0:
cameras += 1 # Root needs camera
return camerasdef tree_dp_generic(root: TreeNode) -> ResultType:
"""
Generic framework for tree DP.
"""
# Global state if answer can be at any node
global_result = initial_value
def dfs(node) -> StateType:
nonlocal global_result
if not node:
return base_state
# Post-order: process children first
left_state = dfs(node.left)
right_state = dfs(node.right)
# Compute current node's state
current_state = transition(left_state, right_state, node.val)
# Update global result if needed
global_result = update_global(global_result, current_state)
return current_state
root_state = dfs(root)
return extract_answer(root_state, global_result)def tree_diameter(root: TreeNode) -> int:
"""
Find longest path between any two nodes.
"""
diameter = 0
def dfs(node):
nonlocal diameter
if not node:
return 0
left = dfs(node.left)
right = dfs(node.right)
# Diameter through this node
diameter = max(diameter, left + right)
# Return height (depth of deepest subtree)
return 1 + max(left, right)
dfs(root)
return diameter| Constraint | States | Return |
|---|---|---|
| Include/exclude | (with, without) | Both |
| Path sum | contribution | Single + global |
| Coverage | (not_covered, covered, has_camera) | State + count |
| Height/depth | integer | Single value |
| Subtree property | (satisfies, info) | Tuple |
Document generated for NeetCode Practice Framework — API Kernel: tree_dp