8.10 Subtree Queries

Many tree problems ask questions about an entire subtree rather than an individual node.

algorithmstreesdata-structures

8.10 Subtree Queries

Many tree problems ask questions about an entire subtree rather than an individual node.

Examples include:

  • What is the sum of all values in this subtree?
  • How many descendants does this node have?
  • What is the maximum value below this node?
  • How many active users belong to this organizational branch?
  • What is the total storage used by a directory and its descendants?

A naive solution traverses the subtree every time a query arrives. This works for small trees, but quickly becomes impractical when the number of queries grows.

The key observation is that subtrees have structure. Once that structure is exploited, many subtree queries become simple range queries on arrays.

This recipe shows how to preprocess a tree so that subtree queries can be answered efficiently.

Problem

You need to answer repeated queries over entire subtrees.

A straightforward DFS per query is too expensive.

Solution

Flatten the tree using an Euler Tour and compute subtree intervals.

Consider this tree:

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

Assign values:

Node Value
0 10
1 5
2 8
3 3
4 4
5 6
6 2

Perform a DFS.

package main

var timer int

func flatten(
    tree [][]int,
    node int,
    tin []int,
    size []int,
    order []int,
) {
    tin[node] = timer
    order[timer] = node
    timer++

    size[node] = 1

    for _, child := range tree[node] {
        flatten(
            tree,
            child,
            tin,
            size,
            order,
        )

        size[node] += size[child]
    }
}

Possible DFS order:

0 1 3 4 2 5 6

Subtree ranges become:

Node Range
0 [0,6]
1 [1,3]
2 [4,6]
3 [2,2]
4 [3,3]
5 [5,5]
6 [6,6]

Every subtree becomes a contiguous interval.

Discussion

The Euler Tour creates an important invariant:

Every descendant of a node appears in a consecutive block.

For node 1:

1
├── 3
└── 4

The DFS order is:

1 3 4

These elements occupy:

[1,3]

in the flattened array.

Therefore:

Subtree Query

becomes:

Range Query

This transformation allows powerful array-based data structures to be used on trees.

Subtree Size Queries

The simplest subtree query is subtree size.

The DFS already computes it:

size[node] += size[child]

For the sample tree:

Node Subtree Size
0 7
1 3
2 3
3 1
4 1
5 1
6 1

Query complexity:

O(1)

No traversal is required after preprocessing.

Subtree Sum Queries

Suppose the flattened order contains:

Index  Node  Value

0      0     10
1      1      5
2      3      3
3      4      4
4      2      8
5      5      6
6      6      2

Build prefix sums.

func prefixSums(values []int) []int {
    prefix := make([]int, len(values)+1)

    for i := range values {
        prefix[i+1] =
            prefix[i] +
            values[i]
    }

    return prefix
}

Range sum:

func rangeSum(
    prefix []int,
    left int,
    right int,
) int {
    return prefix[right+1] - prefix[left]
}

Subtree of node 1:

Range = [1,3]

Calculation:

5 + 3 + 4 = 12

Query time:

O(1)

after preprocessing.

Dynamic Updates

Prefix sums work only when values remain unchanged.

Suppose:

Node 4 += 100

Rebuilding prefix sums after every update becomes expensive.

A Fenwick Tree solves this problem.

type Fenwick struct {
    tree []int
}

Operations:

Point update
Range sum

both run in:

O(log n)

The subtree range:

[tin[node],
 tin[node]+size[node]-1]

becomes a Fenwick Tree query.

The tree disappears from the algorithm.

Only intervals remain.

Subtree Maximum Queries

Replace sums with maximum values.

A Segment Tree becomes appropriate.

Suppose:

Maximum value in subtree(1)

The subtree interval remains:

[1,3]

The Segment Tree answers:

max(5,3,4)

Result:

5

Query complexity:

O(log n)

Update complexity:

O(log n)

The underlying tree structure never needs to be traversed again.

Counting Active Nodes

Consider a user hierarchy.

CEO
├── Team A
└── Team B

Each node contains:

1 = active
0 = inactive

The question:

How many active users
exist below manager X?

becomes:

Sum over subtree interval.

The solution is identical to subtree sum queries.

Many real-world hierarchy systems use exactly this pattern.

Subtree Updates

Sometimes an entire subtree must change.

Example:

Increase all salaries
in a department by 1000.

After Euler Tour:

Update interval.

Instead of:

Visit every descendant.

A Segment Tree with Lazy Propagation performs:

Range update

in:

O(log n)

This technique scales to very large trees.

Offline Subtree Queries

Suppose updates never occur.

In that case, preprocessing can answer many queries immediately.

Examples:

Subtree size
Subtree sum
Subtree minimum
Subtree maximum

The DFS computes everything once.

Future queries become simple table lookups.

Many production systems use this approach when the hierarchy changes infrequently but queries are frequent.

Aggregation During DFS

Not every subtree query requires Euler Tour.

Some values can be computed directly during DFS.

Subtree sums:

func subtreeSum(
    tree [][]int,
    values []int,
    node int,
    sums []int,
) {
    sums[node] = values[node]

    for _, child := range tree[node] {
        subtreeSum(
            tree,
            values,
            child,
            sums,
        )

        sums[node] += sums[child]
    }
}

The recurrence is:

node value
+
sum of child subtrees

After preprocessing:

sums[node]

contains the answer.

Query complexity:

O(1)

This is often simpler than building additional data structures.

Subtree Query Design Pattern

Many subtree algorithms follow the same workflow.

Step 1

Flatten the tree.

Tree
→
Array

Step 2

Identify subtree interval.

[start,end]

Step 3

Choose an interval data structure.

Examples:

Query Type Structure
Sum Prefix Sum
Dynamic Sum Fenwick Tree
Min/Max Segment Tree
Updates Lazy Segment Tree

Step 4

Answer queries on intervals instead of traversing trees.

This pattern appears repeatedly throughout advanced tree algorithms.

Complexity Analysis

Euler Tour preprocessing:

Operation Complexity
DFS flattening O(n)
Subtree sizes O(n)
Entry times O(n)

Prefix sums:

Operation Complexity
Build O(n)
Query O(1)

Fenwick Tree:

Operation Complexity
Update O(log n)
Query O(log n)

Segment Tree:

Operation Complexity
Update O(log n)
Query O(log n)

The choice depends on update frequency and query type.

Common Mistakes

A common mistake is recomputing subtree values for every query.

For:

q queries

this often leads to:

O(nq)

behavior.

Another mistake is forgetting:

end =
tin[node] + size[node] - 1

The missing subtraction creates interval errors.

A third mistake is using a Fenwick Tree for operations that require minimum or maximum values. Fenwick Trees work naturally with invertible operations such as sums, but not with arbitrary range aggregates.

Finally, some implementations flatten the tree correctly but forget to reorder node values into Euler order. The resulting intervals become meaningless.

Takeaway

Subtree queries become efficient when the tree is flattened into an array. Euler Tour converts every subtree into a contiguous interval, allowing array-based data structures to replace repeated tree traversals. Once this transformation is understood, a wide range of hierarchy, aggregation, and update problems reduce to familiar range-query techniques. This idea forms the foundation for many advanced tree algorithms and large-scale hierarchical systems.