Tree & Graph DP

At a glance

The instinct

When a problem lives on a tree and asks for a best / count / minimum over the whole tree, the subtrees are your subproblems. Each subtree is independent of its siblings once you know what happens at its root, so a post-order DFS can compute a small answer per node and hand it upward. The trick is choosing what each node reports: usually one number per "situation" the parent cares about (taken / not taken, covered / uncovered, distance down / count of nodes).

On a general graph this only works when the dependency graph is acyclic - a DAG, or a DAG you build yourself, like the "shortest-path DAG" behind Number of Ways to Arrive at Destination.

Recognise it

Not this pattern if...

• The tree question only needs one value per node with no competing choices (height, size) - that is plain tree DFS.
• The graph has cycles you cannot order (use shortest path / BFS instead of DP).
• You only need a single root-to-leaf path and no aggregation over subtrees - plain recursion or BFS is enough.

Memory hack

Analogy: a company org chart closing its quarterly numbers. Each team lead sends one summary to their manager ("best result if I attend the offsite / if I skip it"). The CEO decides using only the direct reports' summaries.

DP framing:

• State - dp[node][situation], e.g. situation = robbed / not robbed.
• Choice - what the node does (take, skip, place a camera) given what children report.
• Base case - a null child or a leaf returns the neutral report (0 profit, "already covered").
• Order - post-order: children strictly before parent. For rerooting, a second pre-order pass runs parent before children.

Say it out loud in the interview:

1. "What does each subtree need to tell its parent?" - name the states.
2. "How does a parent combine its children's states?" - write the transition.
3. "What does an empty subtree return, and where is the answer - the root, or a global max?"

How it works

Run a DFS. When it returns from a node, all children already have their tuples, so the node combines them in O(children) time. For "answer for every node as the root", do rerooting: first compute down[v] (facts about v's own subtree), then walk from the root downward and convert the parent's full answer into the child's full answer in O(1) per edge.

flowchart TD
    A["Pass 1: post-order DFS"] --> B["Leaves return base tuple"]
    B --> C["Parent combines children tuples"]
    C --> D["Root tuple holds the answer"]
    D --> E{"Need answer for every root?"}
    E -->|"no"| F["Done: read root or global best"]
    E -->|"yes"| G["Pass 2: pre-order DFS"]
    G --> H["child answer = parent answer adjusted by child subtree"]

Worked rerooting idea for Sum of Distances in Tree: when the root moves from u to its child v, the size[v] nodes in v's subtree each get 1 closer and the other n - size[v] nodes each get 1 farther, so ans[v] = ans[u] - size[v] + (n - size[v]).

Java template

import java.util.*;

class TreeDp {
    static class TreeNode {
        int val; TreeNode left, right;
        TreeNode(int v) { val = v; }
    }

    // Post-order tree DP: return one value per state of `node`.
    // Here state 0 = node not used, state 1 = node used (House Robber III shape).
    static long[] dfs(TreeNode node) {
        if (node == null) return new long[]{0, 0};           // base case: empty subtree
        long[] l = dfs(node.left), r = dfs(node.right);       // children first
        long notUsed = Math.max(l[0], l[1]) + Math.max(r[0], r[1]); // kids free to choose
        long used = node.val + l[0] + r[0];                    // problem rule: kids must be unused
        return new long[]{notUsed, used};
    }
}

class Rerooting {
    private List<Integer>[] adj;
    private int[] size;
    private long[] down, ans;
    private int n;

    // Answer "sum of distances from every node" with two DFS passes.
    @SuppressWarnings("unchecked")
    long[] solve(int n, int[][] edges) {
        this.n = n;
        adj = new List[n];
        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
        for (int[] e : edges) { adj[e[0]].add(e[1]); adj[e[1]].add(e[0]); }
        size = new int[n]; down = new long[n]; ans = new long[n];
        collect(0, -1);          // pass 1: facts about each subtree
        ans[0] = down[0];
        distribute(0, -1);       // pass 2: push the full answer to children
        return ans;
    }

    private void collect(int u, int parent) {
        size[u] = 1;
        for (int v : adj[u]) {
            if (v == parent) continue;
            collect(v, u);
            size[u] += size[v];
            down[u] += down[v] + size[v];   // problem-specific merge
        }
    }

    private void distribute(int u, int parent) {
        for (int v : adj[u]) {
            if (v == parent) continue;
            ans[v] = ans[u] - size[v] + (n - size[v]);  // problem-specific shift
            distribute(v, u);
        }
    }
}

Complexity

Variations

• Take / skip states - two numbers per node; parent's choice restricts children. House Robber III.
• Multi-state coverage - three states such as "has camera", "covered without camera", "needs cover". Binary Tree Cameras (a greedy leaf-up view of the same states also works).
• Return one, record another - return the best downward chain, but update a global answer with the path that bends through the node. Binary Tree Maximum Path Sum, Diameter of Binary Tree.
• Rerooting / all-roots DP - down pass then up pass. Sum of Distances in Tree.
• DAG path counting - process nodes in an order where predecessors finish first; for shortest-path counts, Dijkstra pop order is that order. Number of Ways to Arrive at Destination.
• Range-as-subtree - pick a root inside [lo, hi], recurse on both sides and combine. Unique Binary Search Trees II.
• Tree knapsack - each node merges children's "best using k nodes" arrays. Choose k nodes / budgeted subtree problems.

Common mistakes

• Returning a single number when the parent needs to know how the child got it - add a state instead of a global flag.
• In undirected graphs, forgetting the parent argument (or a visited set), causing infinite recursion.
• Recomputing the whole DFS from every root (O(n²)) when one rerooting pass would do.
• Counting paths modulo 1e9+7 but comparing distances as int - shortest-path totals overflow, so use long.
• Assuming deep trees are safe: a 10^5-node chain can overflow Java's default stack; use an iterative order or a bigger thread stack.

All practice problems

5 problems on this site use this pattern, easiest first. Solve them in order and say the instinct out loud before you code.