Euler Tour

The Euler tour technique flattens a tree into an array so that subtrees become contiguous ranges. Once that is done, every array data structure — BIT, segment tree, sparse table — works on trees.

The two flavours

1. Entry/exit times (for subtree queries)

int timer_ = 0;
vector<int> tin, tout;
 
void dfs(int u, int p) {
    tin[u] = timer_++;
    for (int v : adj[u]) if (v != p) dfs(v, u);
    tout[u] = timer_;                     // half-open: subtree = [tin[u], tout[u])
}

The subtree of $u$ occupies exactly [tin[u], tout[u]). Therefore:

Tree operation	Array operation
Subtree sum	range sum on [tin[u], tout[u])
Add $x$ to every vertex in a subtree	range update
Is $u$ an ancestor of $v$?	tin[u] <= tin[v] && tout[v] <= tout[u]
Count distinct values in a subtree	offline range-distinct, or DSU on tree
$k$-th smallest in a subtree	persistent segment tree over the array

2. Full tour with repeats (for LCA)

Record the vertex each time the DFS is at it — on entry and after returning from each child. Length $2n-1$.

vector<int> euler, dep, firstOcc;
 
void dfs(int u, int p, int d) {
    firstOcc[u] = euler.size();
    euler.push_back(u); dep.push_back(d);
    for (int v : adj[u]) if (v != p) {
        dfs(v, u, d + 1);
        euler.push_back(u); dep.push_back(d);
    }
}

$\mathrm{LCA}(u,v)$ is the minimum-depth entry between firstOcc[u] and firstOcc[v] — a range minimum query, answerable in $O(1)$ with a sparse table. See LCA.

3. Edge tour (+1 / −1) for path sums

Push $+w$ at tin[v] and $-w$ at tout[v]. Then a prefix sum up to tin[u] gives the distance from the root to $u$, and subtree updates become point-pair updates:

Operation	Implementation
Add $x$ to the whole subtree of $v$, query a single vertex	range update, point query — BIT with add(tin[v], x), add(tout[v], -x)
Add $x$ to a single vertex, query a subtree sum	point update, range query
Add $x$ along the path $u\to v$, query a vertex	add at $u$, $v$; subtract twice at $\mathrm{lca}$ — then subtree-sum at the end

That last row is the difference array on a tree, and it solves a large class of path-update problems in $O(\log n)$ without HLD.

Why this is such a good trade

A tree has no natural linear order, so tree-specific structures are complicated. The Euler tour buys you a linear order in which the tree’s structure is encoded as intervals — and intervals are what every classical data structure already handles.

tree:            1
                / \
               2   5
              / \
             3   4

tin/tout:  1:[0,5)  2:[1,4)  3:[2,3)  4:[3,4)  5:[4,5)
array:      [1, 2, 3, 4, 5]
             ^--------^      subtree of 1
                ^-----^      subtree of 2

What it does not do

Euler tours handle subtrees cleanly but paths poorly — a root-to-node path is not a contiguous range in the tour. For path queries use binary lifting (queries only) or HLD (queries and updates).

Related structures

• Euler tour trees — keep the tour in a balanced BST so that link and cut become split/merge, giving dynamic subtree queries in $O(\log n)$.
• DSU on tree — uses the Euler order to answer subtree queries offline in $O(n\log n)$ without any range structure.
• Mo’s algorithm on trees — runs Mo’s over the Euler tour to answer path queries offline.

See also: LCA · HLD · Range Query Techniques