8.9 Euler Tour Technique

Many tree problems become dramatically easier when you stop thinking of the tree as a tree.

algorithmstreesdata-structures

8.9 Euler Tour Technique

Many tree problems become dramatically easier when you stop thinking of the tree as a tree.

At first, this sounds strange. Trees are hierarchical structures, so why abandon that structure? The answer is that many efficient algorithms operate on arrays, not trees. Segment Trees, Fenwick Trees, Sparse Tables, Range Minimum Queries, and many caching techniques all expect linear data.

The Euler Tour Technique bridges these two worlds. It transforms a tree into an array while preserving important structural relationships. Once the transformation is complete, subtree queries often become ordinary range queries.

This technique serves as a foundation for subtree aggregation, Lowest Common Ancestor algorithms, Heavy-Light Decomposition, and numerous competitive programming solutions.

Problem

You need to answer subtree queries efficiently.

Examples include:

  • Sum of values in a subtree
  • Maximum value in a subtree
  • Number of descendants
  • Frequency counts
  • Range updates on subtrees

A naive traversal per query is often too expensive.

Solution

Perform a DFS and record the time when each node is entered.

Consider this tree:

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

During DFS:

package main

var timer int

func eulerTour(
    tree [][]int,
    node int,
    tin []int,
    tout []int,
) {
    tin[node] = timer
    timer++

    for _, child := range tree[node] {
        eulerTour(
            tree,
            child,
            tin,
            tout,
        )
    }

    tout[node] = timer
}

The resulting entry times may look like:

Node Entry
0 0
1 1
3 2
4 3
2 4
5 5
6 6

An important property immediately appears:

Subtree(1)
=
{1, 3, 4}

These nodes occupy a contiguous range:

[1, 3]

inside the DFS order.

The subtree becomes an interval.

Discussion

The key insight is simple:

When DFS enters a subtree, it completely finishes that subtree before moving elsewhere.

As a result:

All descendants of a node
appear consecutively
in DFS order.

This property is what makes Euler Tour useful.

Instead of:

Tree problem

we obtain:

Array interval problem

which is often much easier.

Building the Euler Array

A common implementation stores nodes in visitation order.

var timer int

func buildEuler(
    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] {
        buildEuler(
            tree,
            child,
            tin,
            size,
            order,
        )

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

For the sample tree:

0 1 3 4 2 5 6

becomes the Euler order.

Every node now corresponds to a position in an array.

Subtree Ranges

Suppose:

tin[1] = 1
size[1] = 3

The subtree occupies:

[1, 3]

because:

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

For node 2:

tin[2] = 4
size[2] = 3

Range:

[4, 6]

This observation is powerful because subtree queries become ordinary range queries.

Subtree Sum Queries

Suppose each node contains a value.

Node  Value
0     5
1     2
2     7
3     1
4     4
5     3
6     6

Transform the values into Euler order.

Index  Node  Value
0      0     5
1      1     2
2      3     1
3      4     4
4      2     7
5      5     3
6      6     6

Now subtree 1 corresponds to:

[2, 1, 4]

The subtree sum becomes:

2 + 1 + 4 = 7

Instead of traversing the tree, we query a contiguous interval.

A Fenwick Tree or Segment Tree can answer these queries efficiently.

Ancestor Testing

Euler Tour also provides a fast ancestor test.

Node u is an ancestor of node v if:

tin[u] <= tin[v]

and

tout[v] <= tout[u]

Implementation:

func isAncestor(
    u int,
    v int,
    tin []int,
    tout []int,
) bool {
    return tin[u] <= tin[v] &&
        tout[v] <= tout[u]
}

This check runs in constant time.

Without preprocessing, ancestor queries typically require traversal.

Full Euler Tour

The previous approach records only entry times.

Some algorithms require recording both entry and exit events.

For the sample tree:

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

A full Euler Tour produces:

0
1
3
1
4
1
0
2
0

Nodes appear multiple times.

This representation is useful because path relationships become visible in the sequence.

Many LCA algorithms rely on this form.

Euler Tour for LCA

Suppose we record:

  • Euler sequence
  • Depth sequence

Example:

Node:
0 1 3 1 4 1 0 2 0

Depth:
0 1 2 1 2 1 0 1 0

To find:

LCA(3, 4)

Locate the first occurrences:

3 at position 2
4 at position 4

Examine the interval:

2..4

Depth values:

2 1 2

The minimum depth corresponds to:

1

which is exactly the LCA.

This reduces LCA to a Range Minimum Query problem.

Flattening Trees

Euler Tour is often described as:

Flattening the tree

because it converts hierarchical structure into linear structure.

Before:

Tree

After:

Array

Many sophisticated tree algorithms begin with this transformation.

The flattening process allows direct reuse of data structures designed for arrays.

Combining with Fenwick Trees

Suppose we need:

Add 5 to every node
inside a subtree.

Without Euler Tour:

Visit every descendant.

With Euler Tour:

Update one interval.

The operation becomes:

update(
    tin[node],
    tin[node] + size[node] - 1
)

This reduction is one reason Euler Tour appears so frequently in large-scale systems.

Combining with Segment Trees

Suppose each node stores a score.

Queries:

Maximum score in subtree.

After flattening:

Maximum value in interval.

A Segment Tree handles this efficiently.

The tree algorithm disappears.

Only interval processing remains.

This transformation is often the difference between:

O(n)

per query and:

O(log n)

per query.

Complexity Analysis

Let:

  • n = number of nodes

Euler Tour construction:

Operation Complexity
DFS traversal O(n)
Entry times O(n)
Exit times O(n)
Total O(n)

Memory:

Structure Complexity
tin O(n)
tout O(n)
Euler order O(n)

Queries:

Query Complexity
Ancestor test O(1)
Subtree interval lookup O(1)
Subtree range query Depends on data structure

The preprocessing cost is linear.

Common Mistakes

A common mistake is confusing:

Entry time

with:

Position in full Euler Tour

These are different concepts.

Another mistake is forgetting:

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

The subtraction by one is easy to miss and creates subtle off-by-one errors.

A third mistake is using DFS order without guaranteeing that subtrees remain contiguous. The Euler Tour property depends on fully exploring a subtree before visiting another branch.

Finally, some implementations store entry times but forget to compute subtree sizes. Without subtree sizes, interval boundaries become difficult to recover.

Takeaway

Euler Tour transforms a tree into an array while preserving subtree structure. The key property is that every subtree becomes a contiguous interval in DFS order. Once the tree is flattened, many problems that appear hierarchical become ordinary range-query problems. This technique serves as a bridge between tree algorithms and powerful array-based data structures such as Fenwick Trees, Segment Trees, and Range Minimum Query structures.