Skip to content
Tutorials Center
My learning

Topics

Lesson 159 of 225 ยท Dynamic Programming

DP on Trees and DAGs

Learn dynamic programming on trees and DAGs in Python: subtree states, house robber III, tree diameter, rerooting for all roots and longest paths in a DAG.

Most dynamic programming lessons use arrays and tables. But a tree is the most natural DP shape of all: every node's subtree is a smaller copy of the same problem, and subtrees never overlap. So you do not even need a memo table keyed by tricky indexes. You compute something for each child, then combine the answers at the parent.

This lesson shows the template for tree DP, applies it to three classic problems (house robber III, tree diameter, sum of subtree sizes), upgrades it to rerooting (answers for every possible root in O(n)), and finishes with DP on DAGs, where the same idea works because a directed acyclic graph can be processed in topological order.

The template: answer a node from its children

Define the state f(v) as "the answer for the subtree rooted at v". The recipe never changes:

  1. Compute f(child) for each child (recursion, or a reversed pre-order list).
  2. Combine them into f(v).
  3. The answer is f(root) or something collected on the way.
TEXT
            1                post-order: children first, then the parent
          /   \
         2     3             f(4), f(5)  ->  f(2)
        / \     \            f(6)        ->  f(3)
       4   5     6           f(2), f(3)  ->  f(1)

Each node is visited once and combining costs time proportional to its number of children, so the total is O(n). Space is O(h) for the recursion, where h is the tree height.

Python Subtree sizes and sums in one pass

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Recursive tree DP breaks on a path-shaped tree with 100,000 nodes, because Python's default recursion limit is about 1,000. For deep trees, build a visiting order with a stack, then process it in reverse: every child appears after its parent, so the reversed list handles children first. We use that version in the rerooting example below.

Example 1: House Robber III

A thief robs houses arranged as a binary tree. Houses hold money. If the thief robs a house, he cannot rob its direct children (the alarm links parent and child). What is the most money he can take?

Brute force. Try every subset of houses and keep the legal one with the biggest sum: O(2^n). A natural greedy idea ("rob the richest houses first") fails, because one rich house may block two good ones.

Plain recursion. Either rob the node (then add the grandchildren's best) or skip it (then add the children's best). This is correct but recomputes grandchildren many times.

Tree DP with a pair. Return two numbers per node: the best total if you rob this node, and the best total if you skip it. Then the parent only needs its children's pairs.

TEXT
f(v) = (rob, skip)
rob  = value[v] + sum(skip of each child)        children must be skipped
skip = sum(max(rob, skip) of each child)         children are free to choose
Python House Robber III with (rob, skip) pairs

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The pair DP visits each node once: O(n) time and O(h) space. Returning a small tuple to carry "state of this subtree under each choice" is the most common tree-DP pattern: take or skip, colored or not, covered or not. Minimum vertex cover, maximum independent set, and "minimum cameras in a binary tree" are all the same shape with different transitions.

Example 2: the diameter of a tree

The diameter is the number of edges on the longest path between any two nodes. The path may not pass through the root.

Brute force. Run a BFS from every node and keep the largest distance: O(n^2). Fine for 1,000 nodes, hopeless for a million.

Tree DP. Let height(v) be the longest downward path (in edges) starting at v. The best path whose highest node is v joins the two tallest child branches:

TEXT
through(v) = (tallest child height + 1) + (second tallest child height + 1)
height(v)  = tallest child height + 1        (0 for a leaf)
diameter   = max over v of through(v)

Every path has exactly one highest node, so taking the maximum over all nodes covers all paths. This is a nice example of a DP that collects its answer on the side rather than returning it from the root.

Python Tree diameter: BFS brute force versus DP

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A common alternative is two BFS runs: start anywhere, go to the farthest node a, then find the farthest from a. It is also O(n), but it only works when edge weights are non-negative; the DP version handles negative weights and generalises to "best path sum" problems (see tree problems for the binary-tree flavour).

Example 3: rerooting, the answer for every root

Suppose you must find, for every node r, the sum of distances from r to all other nodes. Rooting once and doing DP gives the answer for only that root. Doing it n times costs O(n^2).

Rerooting gets all n answers in two passes:

  1. Down pass (rooted at node 0): compute size[v] and down[v], the sum of distances from v to the nodes in its own subtree: down[v] = sum(down[c] + size[c]).
  2. Up pass: move the root from a parent p to its child c. Nodes inside c's subtree (there are size[c]) get 1 step closer. All other nodes (n - size[c]) get 1 step farther:
TEXT
ans[c] = ans[p] - size[c] + (n - size[c])
TEXT
      p                          p
     / \    move root to c      /       nodes in c's subtree: distance - 1
    c   x   ----------------> c         all the others:       distance + 1
   / \                       / \
Python Sum of distances from every node (rerooting)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The same two-pass idea (compute child contributions downward, then pass "everything outside my subtree" upward) solves "farthest node from each node", "number of nodes at distance k", and many counting problems in O(n).

DP on a DAG

A directed acyclic graph (DAG) is not a tree, because a node can have several parents, so subproblems do overlap. That is exactly when memoization pays off. The DP order is: process nodes in topological order (or recurse with a cache), so a node is evaluated only after everything it depends on.

A classic: given tasks with durations and "must finish before" edges, what is the shortest time to finish everything, with unlimited workers? That is the longest path in the DAG, also called the critical path. The longest path is easy on a DAG even though it is hard (NP-hard) in a general graph, because there are no cycles to loop back through.

TEXT
   design(3) ---> build(5) ---> test(2) ---> ship(1)
        \                          ^
         \--> docs(4) -------------/

best[v] = duration[v] + max(best[u] for each prerequisite u)
Python Critical path: longest path in a DAG

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The cost is O(V + E): each node is computed once, and each edge is looked at once when its target is computed. The same pattern counts the number of paths from a source to every node (replace max with a sum), finds the cheapest path in a DAG with negative edges, and powers build systems and spreadsheets that recompute cells in dependency order.

Common mistakes

  • Forgetting the parent in undirected trees. adj[v] includes the parent, so always skip it (w == parent) or you will recurse forever.
  • Mixing up "includes the node" and "ends at the node". Define the state precisely: the diameter DP returns the best downward path, but stores the best bent path on the side.
  • Recursing too deep. A tree with 100,000 nodes in a chain needs the iterative order shown in the rerooting example.
  • Recomputing instead of returning pairs. If your recursion calls itself on grandchildren and children, return a tuple instead.
  • Assuming a DAG is a tree. A DAG node with two parents is reachable twice, so you must memoize or the cost explodes.

When to use tree DP

Use it when the input is a tree (or can be turned into one) and the answer for a subtree depends only on its children's answers: independent sets, covering problems, path sums, counting arrangements, "what if I cut this edge" questions. If the problem asks for answers about every node as a root, think rerooting. If the input is a DAG, order by dependency and apply the same recurrence. If the graph has cycles, you first need to collapse them (see strongly connected components).

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the time complexity of the (rob, skip) DP for House Robber III?

    Each node is visited once and does constant work with its two children's pairs.
  2. 2. In the diameter DP, what does height(v) return?

    height(v) is the tallest branch below v. The bent path through v, top1 + top2, is recorded separately in best.
  3. 3. When the root moves from parent p to child c, what happens to distances?

    That gives ans[c] = ans[p] - size[c] + (n - size[c]).
  4. 4. Why is the longest path easy on a DAG?

    With no cycles, best[v] depends only on nodes earlier in topological order, so one pass is enough: O(V + E).
  5. 5. Why should deep trees be processed with an explicit stack instead of recursion in Python?

    A path-shaped tree with many nodes would raise RecursionError. A reversed visiting order gives children-before-parents without recursion.

Summary

  • Tree DP: define f(v) for the subtree at v, compute it from the children's values, usually in O(n) total.
  • Return a small tuple (rob/skip, covered/uncovered) when the parent's choice changes what a child may do.
  • Diameter: height returned upward, best bent path top1 + top2 collected on the side; O(n).
  • Rerooting: one down pass and one up pass give the answer for every root in O(n) instead of O(n^2).
  • DAG DP: evaluate in topological order or with a cache; longest path and path counting cost O(V + E).
  • For very deep trees, use an explicit stack and a reversed visiting order instead of recursion.

Next: Optimising DP