Tree DP

Trees have a natural recursive structure: every subtree is itself a tree. Tree DP exploits this by computing answers bottom-up: solve the leaves first, then combine results as you move toward the root. The canonical example is House Robber III, where houses are arranged in a binary tree and you cannot rob both a house and its direct parent or child. The question: what is the maximum amount you can rob?

Why post-order traversal

In a linear house robber problem, you scan left to right, and each house's decision depends only on the previous one or two houses. In a tree, each node's decision depends on its children's answers. You cannot decide whether to rob node A until you know the best outcomes for A's entire left and right subtrees. This forces a post-order traversal: visit children before the parent, leaves before internal nodes, bottom before top.

This is the defining characteristic of tree DP. You root the tree (picking any node as root if the tree is unrooted), run DFS, and on the way back up from each subtree, you compute that node's DP value from its children's already-computed values.

The two-state pattern

For LeetCode 337 (House Robber III), a single value per node is not enough. If you only store "the best you can do in this subtree," the parent does not know whether the child itself was robbed or not, and that matters, because robbing the parent forbids robbing the child.

The solution is to store two values per node: dp[node] = [not_selected, selected]. Here, selected is the best sum if we rob this node, and not_selected is the best sum if we do not rob this node.

The recurrence is clean. If we rob node u, we collect its value but cannot rob any of its children. If we skip node u, we are free to either rob or skip each child, taking whichever is better:

• dp[u][1] = value[u] + sum(dp[child][0] for each child)
• dp[u][0] = sum(max(dp[child][0], dp[child][1]) for each child)

The answer is max(dp[root][0], dp[root][1]).

Walking through a small tree

Consider this tree where each node's value is shown:

        3
       / \
      2    3
       \    \
        3    1

Start at the leaves. Node 3 (bottom-left): dp = [0, 3]. Node 1 (bottom-right): dp = [0, 1].

Move up. Node 2 has one child (the bottom-left 3). If we rob node 2: 2 + 0 = 2. If we skip node 2: max(0, 3) = 3. So dp = [3, 2].

Node 3 (right child of root) has one child (node 1). Rob it: 3 + 0 = 3. Skip it: max(0, 1) = 1. So dp = [1, 3].

Finally, the root (value 3). Rob it: 3 + 3 + 1 = 7. Skip it: max(3, 2) + max(1, 3) = 3 + 3 = 6. The answer is max(6, 7) = 7, which corresponds to robbing the root and both grandchildren.

The code

def rob(root):
    def dfs(node):
        if not node:
            return [0, 0]  # [not_rob, rob]
        left = dfs(node.left)
        right = dfs(node.right)
        not_rob = max(left) + max(right)
        rob_it = node.val + left[0] + right[0]
        return [not_rob, rob_it]

    return max(dfs(root))

Each node is visited exactly once. The DFS naturally processes children before parents. The two-element return value carries both states upward, and the parent combines them in constant time. Time and space are both $O(n)$.

Tree diameter

LeetCode 543 asks for the tree diameter, the longest path between any two nodes, and is another classic tree DP problem. The insight is that the longest path either passes through a given node or it does not. If it passes through node u, it uses the two longest downward paths from u into two different subtrees.

For each node, compute the depth of its deepest descendant in each subtree. The candidate diameter through that node is depth1 + depth2, where depth1 and depth2 are the two largest depths among all children. Track the global maximum across all nodes:

def diameter(root):
    best = 0

    def depth(node):
        nonlocal best
        if not node:
            return 0
        left = depth(node.left)
        right = depth(node.right)
        best = max(best, left + right)
        return 1 + max(left, right)

    depth(root)
    return best

The DFS returns the depth of the deepest path going downward from each node. But at each node, it also considers the path that goes through the node, left depth plus right depth, and updates the global answer. This split between "what I return to my parent" and "what I compute locally" is a recurring theme in tree DP.

The rerooting technique

Sometimes you need the answer not for one fixed root, but for every possible root. Take LeetCode 834: you compute for each node in a tree the sum of distances from that node to all other nodes. A naive approach runs DFS from every node, giving $O(n^2)$. Rerooting reduces this to $O(n)$.

The idea has two phases. First, root the tree at an arbitrary node (say node 0) and compute the answer for that root using standard tree DP. Second, propagate the answer along each edge: when you "move" the root from a parent to a child, some nodes get closer (those in the child's subtree) and others get farther (everything else). You can express the child's answer in terms of the parent's answer with a simple formula.

For the sum-of-distances problem, let ans[u] be the sum of distances from node u to all other nodes, and let sz[u] be the size of u's subtree when rooted at node 0. When you shift the root from parent p to child c, the sz[c] nodes in c's subtree each get one step closer, and the remaining n - sz[c] nodes each get one step farther:

ans[c] = ans[p] - sz[c] + (n - sz[c])

Phase 1 computes ans[0] and all subtree sizes with one DFS. Phase 2 propagates with another DFS from the root downward. Two passes, $O(n)$ total.

def sumOfDistancesInTree(n, edges):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)

    sz = [1] * n
    ans = [0] * n

    # Phase 1: compute sz and ans[0]
    def dfs1(u, parent):
        for v in adj[u]:
            if v == parent:
                continue
            dfs1(v, u)
            sz[u] += sz[v]
            ans[0] += sz[v]  # each node in v's subtree is sz[v] edges from root via v

    # Phase 2: reroot
    def dfs2(u, parent):
        for v in adj[u]:
            if v == parent:
                continue
            ans[v] = ans[u] - sz[v] + (n - sz[v])
            dfs2(v, u)

    dfs1(0, -1)
    dfs2(0, -1)
    return ans

The rerooting technique generalizes beyond distance sums. Any time the answer for a new root can be derived from the answer for an adjacent root in $O(1)$, you can reroot. This works for problems like minimum height trees, distributing coins, and counting good paths.

Binary Tree Cameras (three-state post-order)

Binary Tree Cameras (LC 968) asks you to place the minimum number of cameras on tree nodes so that every node is monitored (a camera covers itself, its parent, and its children). The key insight is a greedy post-order strategy: place cameras as late as possible, at parents of leaves rather than at leaves themselves.

Each node returns one of three states: 0 = needs a camera from its parent, 1 = has a camera, 2 = already covered by a child's camera. Process leaves first. A leaf has no children to cover it, so it returns 0 (needs coverage). Its parent sees a child that needs coverage, so it must place a camera and return 1. A node whose child has a camera is already covered and returns 2.

The rules during post-order:

• If any child returns 0 (needs coverage), this node must place a camera. Return 1.
• If any child returns 1 (has camera), this node is covered. Return 2.
• Otherwise all children are covered but none have cameras aimed at us. Return 0 (ask parent for coverage).

After the DFS, check the root: if it returns 0, it still needs a camera.

def minCameraCover(root):
    cameras = 0

    def dfs(node):
        nonlocal cameras
        if not node:
            return 2  # null nodes count as covered
        left = dfs(node.left)
        right = dfs(node.right)
        if left == 0 or right == 0:
            cameras += 1
            return 1  # place camera here
        if left == 1 or right == 1:
            return 2  # covered by child's camera
        return 0      # not covered, need parent's camera

    if dfs(root) == 0:
        cameras += 1
    return cameras

This greedy approach works because delaying cameras toward the root always covers at least as many nodes per camera. Time and space are both $O(n)$.

Longest ZigZag Path (alternating direction DP)

The Longest ZigZag Path (LC 1372) asks for the longest path in a binary tree where you alternate between going left and going right at each step. At each node, track two values: the length of the zigzag path ending here if we arrived from the left, and the length if we arrived from the right.

When visiting a node, if its left child exists, that child can extend a zigzag that continues to the right, so the child's "arrived from right" length is this node's "arrived from left" length plus one. Symmetrically for the right child. Whenever a direction resets (going left after arriving from left), the zigzag length resets to 1.

def longestZigZag(root):
    best = 0

    def dfs(node):
        nonlocal best
        if not node:
            return (-1, -1)  # (left_length, right_length)
        left_left, left_right = dfs(node.left)
        right_left, right_right = dfs(node.right)
        # If we go left from this node, we extend the right-zigzag of the left child
        go_left = left_right + 1
        # If we go right from this node, we extend the left-zigzag of the right child
        go_right = right_left + 1
        best = max(best, go_left, go_right)
        return (go_left, go_right)

    dfs(root)
    return best

Each node returns (left_length, right_length), the zigzag length if a parent were to arrive here via its left or right pointer. The global maximum is updated at every node. Time and space are $O(n)$.

Complexity

Standard tree DP runs in $O(n)$ time and $O(n)$ space (for the recursion stack and DP arrays), where n is the number of nodes. The rerooting technique adds a second DFS pass but remains $O(n)$. The two-state pattern doubles the constant factor but does not change the asymptotic complexity.

The beauty of tree DP is that trees have no cycles, so there is no risk of revisiting nodes or needing memoization tables indexed by complex state. The tree structure itself provides the DAG ordering: post-order traversal gives you a topological sort for free.

Recognizing this pattern

You're probably looking at tree DP when:

• The input is a tree (or rooted DAG) and the answer at each node aggregates results from its children.
• A node's contribution depends on a choice that conflicts with its parent or children, such as take/skip, color, or camera placement.
• The natural recursion is post-order: compute children first, then combine at the node.
• You might also need to compute an answer for every node as root, the signal for rerooting (two passes).

Common templates:

• Single-direction aggregate: each DFS call returns the best path/sum extending up from this node. Example: Binary Tree Maximum Path Sum.
• Diameter-style: return one value, update a global best from combining children. Example: Diameter of Binary Tree.
• Take-or-skip two-state: return a pair (rob_this, skip_this) so parents can pick the compatible option. Example: House Robber III.
• Multi-state constraint: encode 3+ states per node (has-camera / covered / needs-cover). Example: Binary Tree Cameras.
• Rerooting: two DFS passes to compute the answer with every node as root. Example: Sum of Distances in Tree.