Dynamic Programming

DP on Trees

Each node returns a small tuple of states to its parent (rob/skip, cover/uncovered).

Hard, about 100 minutes to practise.

1Understand

The idea

Let each node return a small tuple of answers for its subtree, one per state, such as (best if I am robbed, best if I am not). The parent combines its children's tuples according to the rule that links neighbouring nodes. One post-order traversal computes everything in O(n).

Intuition

Let each node return a small tuple of answers for its subtree, one per state, such as (best if robbed, best if not). The parent combines children's tuples under the neighbour constraint.

One post-order traversal computes everything in O(n). This is tree DP: the "DAG of subproblems" is the tree itself.

Trying to flatten to an array DP usually means rerooting or Euler tours, overkill until the problem asks for every-node-as-root answers.

What you will be able to do

  • Return multiple states per node
  • Combine children without recomputation

When to use it

  • Tree version of a 1-D DP (house robber III)
  • Choose nodes with parent/child constraints

2See it

Walkthrough

House robber on a tree

Root 3 with children 2, 3, rob node vs skip.

1 / 6

i
3
2
3
012
i → index 1

Post-order: process children before parent. Leaf 2: rob=2, skip=0.

if not node: return (0,0)

Live template

Line 1 active

1def dfs(node):
2 if not node: return (0, 0) # (take, skip)
3 lt, ls = dfs(node.left); rt, rs = dfs(node.right)
4 return (node.val + ls + rs, max(lt, ls) + max(rt, rs))

Complexity: time O(n), space O(h)

Time O(n), space O(h) recursion (plus O(n) if storing per-node pairs). General graph DP with cycles needs different tools (and is often NP-hard).

Read the walkthrough as text

House robber on a tree. Node values; cannot rob both ends of an edge.

  1. For leaf v: (rob=v.val, skip=0).
  2. For internal node: rob = v.val + sum(child.skip); skip = sum(max(child.rob, child.skip)).
  3. Combine at root: max(rob, skip).
  4. Each edge constraint is enforced by forbidding child.rob when parent is robbed.

Return a pair from the DFS; never need a global table indexed by node ids unless rerooting.

3Recognise it

Kinds of problems (6)

Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.

  • Take / skip (house robber III)

    Example. Max sum on tree with no parent-child both taken.

    How. Return (rob, skip) per node; rob = val + left_skip + right_skip.

  • Minimum cameras to cover a tree

    Example. Fewest cameras to watch all nodes.

    How. States covered/uncovered/camera on node; combine child states bottom-up.

  • Longest path with constraints

    Example. Longest zigzag or path with alternating direction.

    How. Per node return lengths in each direction from children.

  • Count unique BSTs (Catalan)

    Example. Number of BSTs with keys 1..n.

    How. dp[n] = sum dp[i-1]*dp[n-i]; classic Catalan on subtree sizes.

  • Generate all trees with memoisation

    Example. All unique BSTs for 1..n.

    How. Memo on (lo, hi) list of roots with recursive left/right tree lists.

  • Flow through subtrees (excess passed to the parent)

    Example. Distribute coins in tree to make each node one coin.

    How. DFS returns excess up; moves += abs(left_excess) + abs(right_excess).

Common mistakes

Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.

  • Grandchild recursion

    Why it happens. Robbing node and skipping children but grabbing grandchildren directly.

    How it fails. House robber III dfs into grandchildren from parent, exponential revisits.

    Fix. Only recurse immediate children; combine their returned tuples.

  • Single state

    Why it happens. One max value per subtree looks enough.

    How it fails. Return only max rob value, parent cannot choose skip path with alternate child takes.

    Fix. Return (rob_subtree, skip_subtree) or richer tuple parent needs.

  • Wrong leaf state

    Why it happens. None child seems like 0 profit always.

    How it fails. None returns (0,0) but leaf should force take vs skip distinction, wrong at single node.

    Fix. Base None as (0,0) for sums; at leaf set rob=val, skip=0 explicitly.

4Check yourself

Concept check

A short quiz on this lesson before you practise. Optional, and it does not gate coding.

Ready to practise?

Mastery comes from solving. The lesson is optional context.

All lessons