13.12 Tree Dynamic Programming

Many dynamic programming problems are defined on linear structures such as arrays, strings, and intervals.

algorithmsdynamic-programming

13.12 Tree Dynamic Programming

Many dynamic programming problems are defined on linear structures such as arrays, strings, and intervals. Tree dynamic programming extends these ideas to hierarchical structures. Instead of moving left to right through a sequence, computation flows through parent-child relationships.

Tree dynamic programming is one of the most important techniques in competitive programming, graph algorithms, compiler construction, network optimization, and computational biology. Problems that appear difficult on general graphs often become tractable when the graph is a tree because trees eliminate cycles and provide a natural decomposition into independent subproblems.

The central idea is simple:

Every subtree is itself a smaller version of the original problem.

This recursive structure makes trees a natural fit for dynamic programming.

Problem

How do we design dynamic programming solutions when the input is a tree rather than a sequence or interval?

Understanding Tree Structure

Consider the tree:

        1
      / | \\n     2  3  4
    / \\n   5   6

Every node defines a subtree.

For example:

Node 2

defines:

    2
   / \\n  5   6

A key observation is that subtrees are independent.

Once information from children has been computed, the parent can often be solved without examining the entire tree again.

This is the foundation of tree dynamic programming.

The Simplest State

The most common state is:

$$ dp[node] $$

Meaning:

The solution for the subtree rooted at this node.

This mirrors familiar patterns from earlier chapters:

Structure State
Array dp[i]
Grid dp[i][j]
Interval dp[l][r]
Tree dp[node]

The difference lies in the dependency graph.

Instead of depending on neighboring indices, a tree node depends on its children.

Example: Subtree Size

Given a tree, compute the number of nodes contained in every subtree.

State:

$$ dp[u] $$

Meaning:

number of nodes
in subtree rooted at u

Every subtree contains:

  • itself
  • all descendants

Recurrence:

$$ dp[u] = 1 + \sum dp[v] $$

for every child:

$$ v $$

of:

$$ u $$

Implementation:

func dfs(u, parent int) {

    dp[u] = 1

    for _, v := range graph[u] {

        if v == parent {
            continue
        }

        dfs(v, u)

        dp[u] += dp[v]
    }
}

This is one of the simplest tree DP examples.

Why DFS Appears Everywhere

Dynamic programming requires dependencies to be computed before the current state.

In trees:

children

must be processed before:

parent

Depth-first search naturally produces this ordering.

The traversal:

go down
solve subtree
return result

matches the dependency structure exactly.

As a result, most tree DP algorithms are implemented using DFS.

Example: Tree Height

State:

$$ dp[u] $$

Meaning:

height of subtree rooted at u

A leaf has height:

$$ 1 $$

A non-leaf node has height:

$$ 1 + \max(dp[v]) $$

over all children.

Recurrence:

$$ dp[u] = 1 + \max_{v} dp[v] $$

Implementation:

func dfs(u, parent int) {

    dp[u] = 1

    for _, v := range graph[u] {

        if v == parent {
            continue
        }

        dfs(v, u)

        dp[u] = max(
            dp[u],
            dp[v]+1,
        )
    }
}

The structure resembles longest-path dynamic programming.

Example: Maximum Path Sum

Suppose each node contains a value.

Goal:

maximum root-to-leaf path sum

State:

$$ dp[u] $$

Meaning:

best path sum
starting at u

Recurrence:

$$ dp[u] = value[u] + \max(dp[v]) $$

for every child.

Again, computation proceeds upward from leaves.

The recurrence differs only in how child results are combined.

Combining Child Information

Most tree DP algorithms follow the same pattern.

For every child:

compute child state

Then:

merge child contribution

This can involve:

  • summation
  • maximum
  • minimum
  • counting
  • custom aggregation

The merge operation defines the problem.

The traversal pattern usually remains unchanged.

Example: Maximum Independent Set on a Tree

This is one of the classic tree DP problems.

An independent set is a collection of nodes such that no two adjacent nodes are selected.

Goal:

maximize number of selected nodes

The challenge is that choosing a node affects decisions in neighboring nodes.

A single state is insufficient.

Multiple States Per Node

Define:

$$ dp[u][0] $$

Meaning:

best answer
if node u is NOT selected

Define:

$$ dp[u][1] $$

Meaning:

best answer
if node u IS selected

Now the dependency becomes explicit.

Node Selected

Children cannot be selected.

$$ dp[u][1] = 1 + \sum dp[v][0] $$

Node Not Selected

Children may choose either option.

$$ dp[u][0] = \sum \max ( dp[v][0], dp[v][1] ) $$

This recurrence solves the problem in linear time.

State Explosion

Tree DP frequently introduces multiple states per node.

Examples:

selected / not selected

black / white

matched / unmatched

visited / unvisited

The state often represents constraints imposed by the parent.

When designing tree DP, ask:

What information about this node affects decisions below it?

The answer usually becomes part of the state.

Bottom-Up Computation

Tree dynamic programming is naturally bottom-up.

Leaves are solved first.

Their results propagate upward.

For example:

      A
     / \\n    B   C
       / \\n      D   E

Computation order:

B
D
E
C
A

Every state becomes available before it is needed.

This is exactly what dynamic programming requires.

Rerooting Dynamic Programming

Some problems ask:

compute answer
for every possible root

A naive solution runs DFS:

n times

leading to:

$$ O(n^2) $$

complexity.

Rerooting DP avoids this by reusing previously computed results.

The idea:

  1. Compute information from children upward.
  2. Propagate information from parents downward.
  3. Combine both sources.

This technique transforms many quadratic algorithms into linear ones.

Example: Sum of Distances

Given a tree:

compute distance sum
from every node
to all others

A naive approach performs BFS from every node.

Complexity:

$$ O(n^2) $$

Rerooting DP solves the same problem in:

$$ O(n) $$

by reusing subtree information.

This is one of the most powerful tree-DP techniques.

Tree DP Versus Graph DP

Trees provide two advantages:

No Cycles

Subproblems are naturally independent.

Unique Parent Relationship

Every node belongs to exactly one subtree.

General graphs lack these properties.

Many graph problems become NP-hard, while their tree versions admit elegant DP solutions.

This difference explains why tree dynamic programming is so widely studied.

Common Patterns

Several state designs appear repeatedly.

Subtree Aggregation

$$ dp[u] = combine(children) $$

Examples:

  • subtree size
  • subtree sum
  • subtree maximum

Include/Exclude

$$ dp[u][0] $$

$$ dp[u][1] $$

Examples:

  • independent set
  • vertex cover
  • matching

Path-Based

$$ dp[u] = best\ path\ through\ u $$

Examples:

  • diameter
  • longest path
  • maximum path sum

Counting

$$ dp[u] = number\ of\ valid\ configurations $$

Examples:

  • colorings
  • labelings
  • arrangements

Common Mistakes

Forgetting the Parent

Undirected trees contain bidirectional edges.

Without:

if v == parent

DFS revisits nodes indefinitely.

Incorrect Merge Logic

The traversal may be correct while the aggregation is wrong.

Always verify the recurrence independently of the DFS.

Missing Leaf Cases

Leaf nodes often define base states.

Incorrect initialization propagates through the entire tree.

Oversized States

A state should contain only information required for future decisions.

Unnecessary dimensions quickly increase complexity.

Complexity Analysis

Let:

$$ n $$

be the number of nodes.

A standard DFS visits every node once.

Time complexity:

$$ O(n) $$

Memory:

$$ O(n) $$

for state storage.

Most classical tree DP problems achieve linear complexity because every edge is processed a constant number of times.

Recognizing Tree Dynamic Programming

Strong indicators include:

  • rooted trees
  • subtree queries
  • parent-child constraints
  • node selection problems
  • path aggregation
  • hierarchical optimization
  • configuration counting on trees

Whenever a problem asks:

solve something
for every subtree

tree dynamic programming should be one of the first techniques considered.

Takeaway

Tree dynamic programming extends the core principles of dynamic programming to hierarchical structures. Each subtree becomes a subproblem, depth-first search provides a natural dependency order, and node states capture the information needed to combine child solutions. Simple subtree aggregations, include/exclude states, rerooting techniques, and path-based recurrences form a toolkit capable of solving a wide range of optimization and counting problems in linear time. Understanding tree DP is an important milestone because many advanced graph algorithms build directly upon these ideas.