DP on Trees: When Recursion Meets Dynamic Programming

I've been breaking down coding patterns that took me too long to understand, writing about the process so it sticks. Dynamic programming on trees had me stuck for weeks.

I could solve DP on arrays without trouble. Longest increasing subsequence, coin change, no issues. Then someone handed me a binary tree and said "find the maximum path sum" and I froze. DP on trees interview questions felt like a different language compared to everything I'd practiced.

The confusing part was not the tree itself. I knew DFS, recursion, and dynamic programming individually. But I could not figure out how they fit together when applied to trees. With arrays, you iterate left to right. With grids, you go top-left to bottom-right. With trees, there is no index, no "previous element." Just nodes pointing to other nodes in every direction.

I was overthinking it. Dynamic programming on trees is recursion with one small twist: you store what your children computed and combine those results at the parent.

Why Trees Break Your DP Intuition

If you have done any amount of DP, your mental model probably looks like this: define a state based on an index, fill in a table from left to right (or bottom to top), and each cell uses values from earlier cells. That model works because arrays have a natural ordering. Index 0 comes before index 1, which comes before index 2.

Trees do not have that. A node might have two children, three children, or none. There is no obvious "direction" to fill in your table. This is where most people get stuck when they first encounter dp on trees interview questions.

Here is the shift that unlocked it for me: in dynamic programming on trees, the subproblems are not "smaller indices." They are subtrees. Every node is the root of its own little subtree, and the answer for that node depends on the answers from its children's subtrees. You do not iterate left to right. You recurse from leaves up to the root. It is postorder traversal, but with purpose.

If you have read my earlier post on state + transition in DP, the same framework applies here. The state is a node. The transition is: combine my children's answers to compute my own. The base case is a leaf node (no children, so the answer is trivial).

The Tree DP Template That Solves 80% of Problems

Once I understood the structure, I realized most tree DP problems follow the same skeleton. Here it is:

def solve(root):
    def dfs(node):
        if not node:
            return 0  # base case

        left = dfs(node.left)
        right = dfs(node.right)

        # Update global answer if needed
        # (for problems asking about paths through nodes)

        # Return the best answer involving this node
        # that can extend upward to the parent
        return some_combination(node.val, left, right)

    result = dfs(root)
    return result

That covers the entire template. The core of dynamic programming on trees comes down to two decisions: what you return up to the parent, and what you track as a global answer. Most tree DP problems require you to figure out exactly those two pieces.

Let me show you how this plays out on real dp on trees interview problems.

Maximum Path Sum in a Binary Tree

This is LeetCode 124 and it appears in dp on trees interview rounds constantly. The problem: given a binary tree where each node has an integer value (possibly negative), find the path with the largest maximum sum. The path does not have to pass through the root, and it can go from any node to any other node.

The tricky part is that "path" here means you cannot branch. You can go left-child to parent to right-child, but you cannot fork. A path is a single chain.

Here is where the two-answer pattern shows up. At each node, you need to think about two different questions:

1. What is the best path that goes THROUGH this node? (left subtree + node + right subtree)
2. What is the best path that ENDS at this node and can extend upward? (node + one child's subtree)

Question 1 is your candidate for the global answer. Question 2 is what you return to the parent.

def max_path_sum(root):
    best = float('-inf')

    def dfs(node):
        nonlocal best
        if not node:
            return 0

        # Get best path sum from each child
        # Use max with 0: if a subtree is negative, don't include it
        left_gain = max(dfs(node.left), 0)
        right_gain = max(dfs(node.right), 0)

        # Path through this node (candidate for global answer)
        path_through = node.val + left_gain + right_gain
        best = max(best, path_through)

        # Return the best single-branch path ending at this node
        return node.val + max(left_gain, right_gain)

    dfs(root)
    return best

Let me trace through a concrete tree to make this click:

Starting from the leaves and working up:

Node 15: no children. left_gain = 0, right_gain = 0. Path through = 15. Returns 15.

Node 7: same logic. Path through = 7. Returns 7.

Node 20: left_gain = 15, right_gain = 7. Path through = 20 + 15 + 7 = 42. Returns 20 + max(15, 7) = 35.

Node 9: no children. Path through = 9. Returns 9.

Node -10: left_gain = 9, right_gain = 35. Path through = -10 + 9 + 35 = 34. Returns -10 + max(9, 35) = 25.

The global best maximum sum is 42 (the path 15 to 20 to 7). Notice how the answer came from a subtree, not the root. This is why tracking the global answer separately matters in dynamic programming on trees.

House Robber III

LeetCode 337. You are a burglar (a classic setup) and houses are arranged in a binary tree. If you rob a house, you cannot rob its direct children. Find the maximum money you can steal.

This is a classic "include or exclude" DP, but on a tree. At every node, you have two choices:

1. Rob this node: you get its value, but you CANNOT rob its children (you can rob its grandchildren)
2. Skip this node: you take the best your children can offer

def rob(root):
    def dfs(node):
        if not node:
            return (0, 0)  # (rob_this, skip_this)

        left_rob, left_skip = dfs(node.left)
        right_rob, right_skip = dfs(node.right)

        # If we rob this node, children must be skipped
        rob_this = node.val + left_skip + right_skip

        # If we skip this node, children can be robbed or skipped
        skip_this = max(left_rob, left_skip) + max(right_rob, right_skip)

        return (rob_this, skip_this)

    return max(dfs(root))

The key insight: each DFS call returns a tuple. Not just one number, but two. The "rob this node" answer and the "skip this node" answer. The parent needs both to make its own decision.

This pattern of returning multiple values from the DFS is something I did not see in any array DP problem, and it stumped me the first time. Once you recognize it, you spot it everywhere in dp on trees interview problems. Anytime a node's decision affects what its parent can do, you need to pass multiple states up.

I covered a similar multi-state idea in my post on multi-dimensional DP states. The principle is identical, just applied to a tree instead of an array.

The Rerooting Pattern: When Every Node Could Be the Root

Standard tree DP roots the tree at one node and computes answers bottom-up. But some problems ask: "what if every node were the root?" For example: find the node that minimizes the total distance to all other nodes.

The brute force approach runs a full DFS from every node, giving O(n²). The rerooting technique does it in O(n) with two passes.

Pass 1 (standard post-order DFS): root the tree at node 0 and compute the answer for node 0 using normal tree DP. Along the way, store each node's subtree size and contribution.

Pass 2 (pre-order re-root): for each edge from parent to child, mathematically shift the root from parent to child. When you move the root from a parent to its child, the child's subtree gets closer (all those nodes are now "above" the root), and everything outside the child's subtree gets farther. You can express this as a simple formula using the subtree sizes you computed in Pass 1.

def sum_of_distances(n, edges):
    # Build adjacency list
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)

    subtree_size = [1] * n
    dist_sum = [0] * n

    # Pass 1: compute subtree sizes and distance sum for root 0
    def post_order(node, parent):
        for child in adj[node]:
            if child != parent:
                post_order(child, node)
                subtree_size[node] += subtree_size[child]
                dist_sum[node] += dist_sum[child] + subtree_size[child]

    # Pass 2: re-root from parent to child
    def pre_order(node, parent):
        for child in adj[node]:
            if child != parent:
                dist_sum[child] = dist_sum[node] - subtree_size[child] + (n - subtree_size[child])
                pre_order(child, node)

    post_order(0, -1)
    pre_order(0, -1)
    return dist_sum

The first time I saw this technique, it felt like a magic trick. You compute one root's answer the hard way, then get every other root's answer for free using arithmetic. It is the kind of optimization that makes you appreciate how much structure trees actually give you.

How to Recognize Tree DP Problems in Interviews

After working through a dozen dp on trees interview problems, I started noticing consistent signals:

When it is NOT tree DP: If the problem is asking for a simple traversal result (sum of all nodes, count of leaves), regular DFS is enough. If the problem involves a graph with cycles, you are in different territory. If the optimal choice at each node is independent of other nodes, a simple greedy traversal works.

Common Mistakes I Made (And You Probably Will Too)

If you have seen the DP template I use across problems, tree DP is that same template adapted for recursive structures instead of iterative ones.

What to Practice Next

Here are problems that build on these patterns, ordered from approachable to challenging:

1. Diameter of Binary Tree (LeetCode 543) — the simplest tree DP problem. A warm-up for the max path sum pattern.
2. Binary Tree Maximum Path Sum (LeetCode 124) — the full version of what we walked through above.
3. House Robber III (LeetCode 337) — the include/exclude pattern on trees.
4. Longest Univalue Path (LeetCode 687) — similar to diameter, but with a matching constraint.
5. Sum of Distances in Tree (LeetCode 834) — the rerooting technique. This one is hard, but if you understood the concept above, you have all the tools.
6. Binary Tree Cameras (LeetCode 968) — a three-state tree DP problem. Tough but rewarding.

Start with the first two before attempting rerooting. The fundamentals of dynamic programming on trees need to feel automatic before the optimization tricks make sense. These six problems cover the patterns that appear most often in dp on trees interview rounds.

This problem pattern came from working through Levelop's coding patterns track, where tree problems are sequenced to build on each other naturally.