Euler Tour Technique

Flattening a tree into an array by recording entry and exit times, turning subtree and path problems into range problems.

Linearizing a tree

The Euler tour technique records the order in which a depth-first traversal enters and leaves each node, producing an array in which every subtree occupies a contiguous range. This maps tree structure onto array indices so that a subtree query becomes a range query answerable by a Fenwick or segment tree.

Two common encodings

Kronos motion — classical

In/out times: record tin[v] on entry and tout[v] on exit; the subtree of v is exactly the index range [tin[v], tout[v]]. Ideal for subtree add and subtree sum.
Full tour (2n entries): append the node both on entry and on each return; used with a range-minimum structure to answer LCA as the shallowest node between two positions.

Computing in/out times

python

timer = [0]
tin = [0]*n; tout = [0]*n
def dfs(u, parent):
    tin[u] = timer[0]; timer[0] += 1
    for w in adj[u]:
        if w != parent:
            dfs(w, u)
    tout[u] = timer[0]; timer[0] += 1

What it enables

With in/out times, adding a value to a whole subtree is a range update and querying a subtree total is a range query, both O(log n). Combined with the full-tour encoding and a sparse table, LCA queries drop to O(1) after linear preprocessing.

Relationship to HLD

Euler tour handles subtree-based queries cleanly; heavy-light decomposition handles path-based queries. Many tree problems use one, the other, or both, choosing the layout that makes the required operation a contiguous range.