# Tree Dynamic Programming Interview Patterns: Diameter, Path Sum & House Robber

Source: https://www.techinterview.org/post/3233462024/tree-dp-interview-patterns/
Updated: 2026-04-16 · techinterview.org

## 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

- [Databricks Interview Guide](https://techinterview.org/databricks-interview-guide/)

- [Atlassian Interview Guide](https://techinterview.org/atlassian-software-engineer-interview/)

- [LinkedIn Interview Guide](https://techinterview.org/linkedin-software-engineer-interview/)

- [Uber Interview Guide](https://techinterview.org/uber-software-engineer-interview/)

- [Apple Interview Guide](https://techinterview.org/apple-software-engineer-interview/)

- [Meta Interview Guide](https://techinterview.org/meta-software-engineer-interview/)