8.4 Recursion on Trees

Most tree algorithms are recursive, not because recursion is elegant, but because trees are recursive objects. Every subtree is itself a tree. If you know how to solve a problem for a subtree, you often know how to solve it for the entire structure.

This observation is the foundation of nearly every advanced tree algorithm. Tree dynamic programming, Lowest Common Ancestor preprocessing, Heavy-Light Decomposition, Centroid Decomposition, syntax tree evaluation, and many other techniques begin with the same question:

If I already know the answer for every child, how do I compute the answer for the parent?

This recipe develops the recursive mindset that underlies tree algorithms.

Problem

You need to solve a problem on an entire tree by combining solutions from smaller subtrees.

Solution

Think recursively.

Instead of asking:

How do I solve this tree?

Ask:

If I already solved every child subtree, what remains?

Consider the problem of counting nodes.

func countNodes(tree [][]int, node int) int {
    total := 1

    for _, child := range tree[node] {
        total += countNodes(tree, child)
    }

    return total
}

The algorithm counts the current node, then recursively counts every child subtree.

For this tree:

0
├── 1
│   ├── 3
│   └── 4
└── 2

The recursion unfolds naturally:

count(3) = 1
count(4) = 1
count(1) = 1 + 1 + 1 = 3
count(2) = 1
count(0) = 1 + 3 + 1 = 5

The parent simply combines the results from its children.

Discussion

Most recursive tree algorithms follow one of three patterns:

Aggregate information upward.
Propagate information downward.
Combine both directions.

Understanding these patterns is more important than memorizing individual algorithms.

Pattern 1: Aggregating Upward

In this pattern, each child computes information and returns it to its parent.

Height computation is a classic example.

func height(tree [][]int, node int) int {
    maxHeight := 0

    for _, child := range tree[node] {
        h := height(tree, child)

        if h > maxHeight {
            maxHeight = h
        }
    }

    return maxHeight + 1
}

Leaves return:

Internal nodes compute:

1 + maximum child height

Information flows upward from descendants toward the root.

Many algorithms follow this pattern:

Subtree size
Tree height
Tree diameter
Dynamic programming on trees
Expression evaluation

Pattern 2: Propagating Downward

Sometimes information originates at the root and moves toward descendants.

Depth calculation is an example.

func depth(
    tree [][]int,
    node int,
    currentDepth int,
    depths []int,
) {
    depths[node] = currentDepth

    for _, child := range tree[node] {
        depth(
            tree,
            child,
            currentDepth+1,
            depths,
        )
    }
}

The root starts with:

depth = 0

Each child receives:

parent depth + 1

Information moves downward through the tree.

Examples include:

Depth computation
Prefix sums on trees
Path labels
Inherited constraints
State propagation

Pattern 3: Combining Both Directions

Many advanced algorithms require information from both ancestors and descendants.

Suppose every node needs:

Its subtree size.
The size of the entire tree outside that subtree.

The subtree size travels upward.

The remaining-node count travels downward.

This creates a two-pass solution:

Pass 1: child → parent
Pass 2: parent → child

Rerooting algorithms, tree DP optimizations, and many competitive programming problems rely on this pattern.

Recursive Thinking

Beginners often focus on the traversal itself.

Experienced algorithm designers focus on the return value.

Consider this function:

func solve(node int) int

The important question is not:

What does this function do?

The important question is:

What information should this function return to its parent?

For subtree size:

func solve(node int) int {
    return subtreeSize
}

For height:

func solve(node int) int {
    return height
}

For expression trees:

func solve(node int) int {
    return evaluatedValue
}

For dynamic programming:

func solve(node int) State {
    return optimalState
}

The return value defines the recursion.

Once that value is chosen correctly, the implementation is often straightforward.

Example: Expression Trees

Consider this expression:

(3 + 4) * 5

It can be represented as:

      *
     / \\n    +   5
   / \\n  3   4

A recursive evaluator is almost identical to the mathematical definition.

type Node struct {
    Op    string
    Value int
    Left  *Node
    Right *Node
}

func evaluate(node *Node) int {
    if node.Op == "" {
        return node.Value
    }

    left := evaluate(node.Left)
    right := evaluate(node.Right)

    switch node.Op {
    case "+":
        return left + right
    case "*":
        return left * right
    }

    panic("unknown operator")
}

The tree structure directly determines the recursion.

This is one reason trees appear so frequently in compiler design and symbolic computation.

Example: Maximum Value in a Tree

Suppose every node stores an integer value.

type Node struct {
    Value    int
    Children []*Node
}

Finding the maximum value requires only a small modification to the recursion.

func maximum(node *Node) int {
    best := node.Value

    for _, child := range node.Children {
        candidate := maximum(child)

        if candidate > best {
            best = candidate
        }
    }

    return best
}

Again, each subtree computes its own answer and returns it upward.

The parent combines those answers.

Designing Recursive Tree Algorithms

A useful design process consists of four questions.

Question 1

What does a node need to know?

Examples:

Height
Subtree size
Maximum value
Optimal DP state

Question 2

What information can children provide?

Examples:

Child heights
Child sizes
Child DP states

Question 3

How does the parent combine those results?

Examples:

Maximum
Minimum
Sum
Merge
Custom transition

Question 4

What should a leaf return?

The leaf is the base case.

Examples:

Height = 1
Size = 1
Sum = value

Once these questions are answered, the recursive structure usually emerges naturally.

Complexity Analysis

Assume:

n nodes
n - 1 edges

A well-designed recursive traversal visits each node once.

Operation	Complexity
Subtree size	O(n)
Height	O(n)
Maximum value	O(n)
Expression evaluation	O(n)

Each node performs a constant amount of work plus the work of its children.

This gives linear complexity.

The recursion stack requires:

Tree Shape	Stack Depth
Balanced	O(log n)
Degenerate chain	O(n)

Deep trees may require iterative implementations when stack growth becomes problematic.

Common Mistakes

A common mistake is recomputing the same subtree repeatedly.

Consider:

height(left)
height(right)
height(left)

The second call to height(left) repeats work unnecessarily.

Store intermediate results when they are needed more than once.

Another mistake is choosing the wrong return value.

Suppose you need subtree size but return depth instead.

The recursion may still compile and run, but the parent lacks the information it actually needs.

The return value should represent exactly what the parent requires.

A third mistake is forgetting the base case.

Leaves often appear trivial, but every recursive definition depends on them.

An incorrect leaf value usually propagates through the entire computation.

Takeaway

Tree recursion works because every subtree is itself a complete tree. Most algorithms can be understood as information flowing upward from descendants, downward from ancestors, or both. When designing a recursive tree algorithm, focus first on what each node should return to its parent. Once that contract is defined, the traversal often becomes a direct translation of the problem's recursive structure.