Tree DP extends dynamic programming from linear sequences to hierarchical structures. Instead of an array index, the state lives at a node of a tree, and each node's answer is computed from the answers of its children.

Most of this chapter covers tree DP, which is the most common variant in coding interviews. A short section at the end covers DP on more general graphs (DAGs, all-pairs shortest paths).

In tree DP, states live at nodes of a tree, and each node looks downward at its children. The subproblems at the leaves are solved first (they have no children, so their answers are immediate), then work moves upward, combining children's results at each parent until reaching the root. The differences from array DP:

Not every tree problem requires DP. A plain traversal or BFS handles most tree questions. Tree DP becomes necessary when these signals appear:

Common problem types that use tree DP:

If each node's decision depends on what its children decide, it is a tree DP problem.

The central pattern in tree DP: each node returns multiple values to its parent, and the parent combines its children's values to compute its own.

Multiple Return Values

Consider a problem where each node is either "selected" or "not selected," and selecting a node forbids selecting its children (the House Robber constraint). A single returned value cannot encode both options, so the parent cannot decide. Each recursive call instead returns a pair, "best if this child is selected" and "best if not selected," giving the parent everything it needs to combine. This is the "return a pair" pattern.

Post-Order Traversal

Tree DP is implemented with post-order traversal: solve both subtrees, then process the current node. The numbers in the diagram show the order:

By the time any node is processed, all of its descendants have already been solved.

The General Template

The pseudocode that nearly every tree DP problem follows:

The way children's results are combined changes from problem to problem, but the skeleton stays the same.

Problem Statement

A thief has found a new neighborhood to rob. The houses form a binary tree. Each node represents a house with a certain amount of money. The constraint: if you rob a house, you cannot rob its direct children (they are connected by an alarm system). Find the maximum amount of money that can be robbed.

This is the tree version of the House Robber problem. In the array version, adjacent houses cannot both be robbed. Here, a node and its direct children cannot both be robbed.

Intuition

At each node we choose to include or exclude its value:

Option 1: Rob this house. Collect the money at this node and skip both children. The grandchildren (the children's children) remain available.

Option 2: Skip this house. Collect nothing here, but either or both children can be robbed (each child independently makes its own rob/skip decision).

This is the "return a pair" pattern. Each node returns two numbers:

For a leaf node: rob = node.val, skip = 0.

For an internal node:

The answer is max(root.rob, root.skip).

Step-by-Step Trace

A trace through this tree:

The values are [3, 2, 3, null, 3, null, 1].

Processing happens in post-order (leaves first, root last):

The optimal strategy is to rob the root (3) and the two grandchildren (3 and 1), totaling 7.

Red nodes are robbed, yellow nodes are skipped. No red node is adjacent to another red node.

Implementation

Complexity Analysis

This is a major improvement over the naive approach, which re-traverses subtrees repeatedly without memoization and runs in exponential time. Each node is visited once; the "return a pair" pattern avoids redundant traversals by passing all required information upward.

House Robber III used the "return a pair" pattern because the parent needs both possibilities (rob this node, skip this node) to make its own decision. A different family of tree problems has a single value flowing back to the parent, but the answer is the maximum of some other quantity computed at each node along the way. The DFS returns one value for combining and updates a separate global for the answer.

The two canonical examples are Diameter of Binary Tree and Binary Tree Maximum Path Sum. Both have the same shape: the function recursively returns "the best path that goes through this node and continues up to its parent," while a side-effect updates the global "best path that turns at this node."

Diameter of Binary Tree (LC 543)

The diameter of a binary tree is the length of the longest path between any two nodes, measured in edges. The path is not required to pass through the root.

For a node u with subtrees that return leftDepth and rightDepth (each meaning "the longest downward path from a child, in edges"), two quantities matter:

The parent does not need to know about the local-answer value; it only needs the upward-combining value. So the recursive function returns one number, and the diameter is tracked in a class field updated on every call.

The units require care. depth returns the number of edges from node down to its deepest descendant, which is 0 for a leaf. The local path turning at u therefore uses left + right edges, not left + right + 1.

Binary Tree Maximum Path Sum (LC 124)

A path in a binary tree starts at any node, ends at any node, and moves between adjacent nodes. Each node has an integer value (possibly negative). Return the maximum sum of values on any path.

This is structurally identical to Diameter, with three differences:

The same "return one value, update a global" template handles it.

The Math.max(0, ...) clipping is the difference from Diameter: if a subtree's best downward path is negative, skipping it produces a larger sum than extending into it. The local answer at each node is the through-node path sum, and best is the maximum of these over the entire tree.

When To Use This Pattern Vs. Return-A-Pair

The two patterns answer different questions:

When one value in a returned pair is never used by the parent, the second pattern applies and a global update is cleaner. When a global holds a value the parent also needs, the first pattern applies and that value should become part of the return tuple.

The patterns above compute one final answer per tree. A different family of problems asks for an answer at every node that depends on the entire tree. The naive approach (re-run the post-order DFS rooted at every node) is O(n^2). The rerooting technique reduces this to O(n) with two DFS passes.

The canonical example is Sum of Distances in Tree (LC 834): given an undirected tree on n nodes, return an array ans where ans[u] is the sum of distances from u to every other node.

The Two-Pass Structure

Pick an arbitrary root (say node 0) and do two passes.

Pass 1 (downward): for each node, compute the answer assuming the root is the chosen root.

Both arrays fill in via a standard post-order DFS:

After pass 1, sumDown[root] is the answer for the root, but every non-root u has sumDown[u] covering only its subtree, not the rest of the tree.

Pass 2 (rerooting): propagate the answer from each parent to its children, adjusting for the fact that switching the root changes who is on which side.

If u is the current node and we move the root from u to a child v:

So:

ans[v] = ans[u] - count[v] + (n - count[v])

A pre-order DFS starting from the root with ans[root] = sumDown[root] fills ans for every node in O(n).

Implementation

Why Rerooting Works

The first pass builds the answer for one fixed root. The second pass exploits the fact that adjacent nodes' answers differ by a small, local adjustment: moving the root by one edge only changes the distance contribution of two disjoint sets of nodes (the new-child-subtree side and the rest). Recomputing from scratch at every node would be O(n) per node; the reroot trick reduces the per-node work to O(1) once both count and the previous answer are known.

When To Use Rerooting

Use the reroot pattern when:

Beyond Sum of Distances, rerooting solves problems like "for each node u, what is the longest path in the tree starting at u" and "for each node u, what is the maximum sum of values reachable within k edges of u."

Tree DP works because a tree has a clear ordering: leaves first, root last. General graphs do not have this ordering, and cycles break the dependency structure that makes DP work at all. DP on graphs is therefore restricted to three cases: directed acyclic graphs (DAGs), shortest-path formulations that absorb cycles via relaxation, and all-pairs shortest paths via an intermediate-node state.

DAG DP

A DAG has a topological order, which is the graph generalization of "left to right" for arrays. DP on a DAG processes nodes in topological order, and each node's value is computed from its predecessors.

The canonical problems are:

Iteration order matters. Compute a topological order with Kahn's algorithm or DFS, then walk the order once, updating each successor as you go. The complexity is O(V + E), strictly better than Bellman-Ford on cyclic graphs because the topological order eliminates the need for repeated relaxation passes.

Bellman-Ford As DP Over Edge Count

Bellman-Ford computes single-source shortest paths in graphs with negative edge weights (no negative cycles). It is a DP whose state is dp[i][v] = "shortest path from source to v using at most i edges." The recurrence relaxes every edge i times:

dp[i][v] = min( dp[i-1][v], min over edges (u, v) of dp[i-1][u] + w(u, v) )

The DP table dimension is (V) x (V), but the standard implementation collapses to a 1D array dp[v] updated in place across V - 1 passes. This works because any shortest path uses at most V - 1 edges; if a V-th pass still updates anything, a negative cycle exists. The full algorithm runs in O(V x E) time.

Floyd-Warshall As DP Over Intermediate Nodes

Floyd-Warshall computes shortest paths between every pair of nodes. The state is dp[k][i][j] = "shortest path from i to j using only nodes {1, ..., k} as intermediate vertices." The recurrence:

dp[k][i][j] = min( dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j] )

The k dimension can be collapsed because every cell read at layer k either uses no k (so layer k-1 and k agree) or uses k exactly once at the i-k or k-j endpoint (also unchanged by the in-place update). The result is the three nested loops with the k loop outermost: O(V^3) time, O(V^2) space.

When DP On A Graph Is Just BFS Or Dijkstra

Plenty of graph problems look like DP candidates but resolve to standard shortest-path algorithms:

A short guide: if the graph has cycles and edge weights are non-negative, use Dijkstra. If cycles and negative weights, use Bellman-Ford. If acyclic, a topological-order DP gives the best complexity. DP is the better fit for path counting and tree problems, where no specialized shortest-path algorithm applies.