Euler Tour Technique, in depth

Three things called an Euler tour

‘Euler tour’ refers to three related sequences, and code and papers do not always say which one they mean.

The full walk is the graph-theoretic Euler tour of the tree with every edge doubled, which is where the name comes from. For most data-structure work the entry-order form is enough and is the simplest: one array of length n, two integers per vertex. The rest of this page uses it, with a bracket-style update for path sums.

Entry and exit times turn subtrees into slices

Run a DFS from the root with a counter. When you enter vertex v, set tin[v] to the counter and increment it. When you leave v, set tout[v] to the counter minus one, which is the largest entry time of any vertex in v’s subtree. Because a DFS finishes a whole subtree before moving on, the subtree of v is exactly the vertices whose entry time lies in [tin[v], tout[v]], and it has tout[v] − tin[v] + 1 vertices.

In the example tree, root 0 has children 1, 2 and 3; vertex 1 has children 4 and 5; vertex 3 has child 6. Visiting children in that order gives entry order 0, 1, 4, 5, 2, 3, 6. So tin = [0, 1, 4, 5, 2, 3, 6] and tout = [6, 3, 4, 6, 2, 3, 6], indexed by vertex. The subtree of 1 is indices 1..3, which hold vertices 1, 4 and 5. The subtree of 3 is indices 5..6, vertices 3 and 6.

The ancestor test falls out immediately: u is an ancestor of v (counting v as its own ancestor) exactly when tin[u] ≤ tin[v] ≤ tout[u]. That is O(1) with no extra structure, and it is the most widely used single trick from this technique. Binary-lifting LCA uses it as its inner check.

An iterative DFS that does not overflow

A recursive DFS is the natural way to write this, and it fails on deep trees. A path-shaped tree of 10⁵ vertices exceeds Python’s default recursion limit of 1,000 and can overflow the native stack in Java or C++ too. Real trees, such as org charts, file systems, comment threads and dependency graphs, are often deep in places. Write it iteratively with an explicit stack and a per-vertex child pointer, as in iterative DFS with a stack:

def euler_tin_tout(n, adj, root=0):
    """adj: undirected adjacency lists. Returns tin, tout, order, parent, depth."""
    tin, tout, order = [0] * n, [0] * n, []
    parent, depth, it = [-1] * n, [0] * n, [0] * n
    parent[root] = root                 # sentinel so the root never revisits itself
    tin[root] = 0; order.append(root); timer = 1
    stack = [root]
    while stack:
        v = stack[-1]
        if it[v] < len(adj[v]):
            u = adj[v][it[v]]; it[v] += 1
            if u == parent[v]:
                continue
            parent[u], depth[u] = v, depth[v] + 1
            tin[u] = timer; order.append(u); timer += 1
            stack.append(u)
        else:
            tout[v] = timer - 1         # last entry time inside v's subtree
            stack.pop()
    parent[root] = -1
    return tin, tout, order, parent, depth

The per-vertex pointer it[v] makes this O(n) overall: each adjacency entry is looked at once. Pushing all children at once is a common shortcut that gives a valid preorder but makes it hard to know when a vertex is finished, so tout comes out wrong. Keep the pointer form.

Subtree queries and updates with a Fenwick tree

With subtrees as slices, put each vertex’s value at position tin[v] of a Fenwick tree. A subtree sum is a range sum, and a change to one vertex is a point update. Both are O(log n).

class Fenwick:
    def __init__(self, n):
        self.n, self.t = n, [0] * (n + 1)
    def add(self, i, x):                  # position i, 0-based
        i += 1
        while i <= self.n:
            self.t[i] += x; i += i & -i
    def prefix(self, i):                  # sum of positions [0, i)
        s = 0
        while i > 0:
            s += self.t[i]; i -= i & -i
        return s
    def range_sum(self, l, r):            # sum of positions [l, r]
        return self.prefix(r + 1) - self.prefix(l)

class SubtreeSums:
    def __init__(self, n, adj, values, root=0):
        self.tin, self.tout, *_ = euler_tin_tout(n, adj, root)
        self.bit = Fenwick(n)
        for v in range(n):
            self.bit.add(self.tin[v], values[v])
    def point_add(self, v, x):
        self.bit.add(self.tin[v], x)
    def subtree_sum(self, v):
        return self.bit.range_sum(self.tin[v], self.tout[v])

With values [5, 3, 2, 7, 1, 4, 6] on vertices 0..6 of the example tree, subtree_sum(1) is 3 + 1 + 4 = 8, subtree_sum(3) is 7 + 6 = 13 and the whole tree sums to 28. These numbers come from running the code above.

The reverse problem, adding x to every vertex of a subtree and reading single vertices, uses a difference array: add x at tin[v] and −x at tout[v] + 1, and a vertex’s value is the prefix sum up to its own tin. For both range updates and range queries on subtrees, use a segment tree with lazy propagation over the same array; this also handles subtree minimum, maximum and assignment, which a Fenwick tree cannot.

Root-to-node path sums with the plus and minus trick

Path queries are not slices of the entry-order array, but root-to-vertex paths have a neat trick. Put +x at tin[v] and −x at tout[v] + 1 for each vertex value x. The prefix sum up to tin[u] now counts x exactly when u lies inside v’s interval, which means v is an ancestor of u. That is the sum of values on the path from the root to u.

class PathSums:
    """Root-to-v path sums with point updates, O(log n) each."""
    def __init__(self, n, adj, values, root=0):
        self.tin, self.tout, *_ = euler_tin_tout(n, adj, root)
        self.bit = Fenwick(n + 1)             # +1 slot for tout + 1 == n
        for v in range(n):
            self.point_add(v, values[v])
    def point_add(self, v, x):
        self.bit.add(self.tin[v], x)
        self.bit.add(self.tout[v] + 1, -x)
    def root_path_sum(self, v):
        return self.bit.prefix(self.tin[v] + 1)

On the example, the path 0 → 1 → 5 sums to 5 + 3 + 4 = 12, and 0 → 3 → 6 to 5 + 7 + 6 = 18. A path between any two vertices u and w then follows from the LCA: path(u) + path(w) − 2 · path(lca) + value(lca). Path updates combined with path queries, or path maximum, need heavy-light decomposition instead, because the sum trick depends on subtraction.

Lowest common ancestor in one paragraph

The full walk of length 2n − 1, paired with the depth at each position, reduces lowest common ancestor to range minimum: the LCA of u and v is the shallowest vertex in the walk between their first occurrences. With a sparse table that gives O(n log n) preprocessing and O(1) queries. The derivation, a worked example and a comparison with binary lifting and Tarjan’s offline method are in lowest common ancestor algorithms; the Cartesian tree page shows the opposite reduction, from range minimum back to LCA.

Failure modes

Mixing vertex ids and positions. The single most common bug is indexing the Fenwick tree with v instead of tin[v], or reading order[i] where tin[v] was meant. Name them differently: pos for array indices, v for vertices.

Off-by-one on tout. Some code stores tout as the counter after the subtree (exclusive) and some as the last entry time (inclusive). Mixing conventions loses or double-counts one vertex. Pick one, write it in a comment, and test with a single-vertex subtree.

Forgetting the extra slot. The −x update at tout[v] + 1 can equal n for the root and the last branch. Size the Fenwick tree n + 1 or guard the write.

Recursion depth. A recursive DFS passes every random test and then fails on a path-shaped production tree. Use the iterative version or test with a 10⁵-vertex chain.

Changing tree shape. The flattening is static. Inserting a leaf is fine if you can tolerate rebuilding, but moving a subtree to a new parent invalidates every interval after it. For trees that change shape, use Euler-tour trees on balanced binary search trees, or link-cut trees, or rebuild periodically and buffer changes.

Forests and disconnected input. Running from one root misses other components, and their tin values stay 0, which silently aliases them to the root. Run the DFS from every unvisited vertex with a shared counter, or check that the order has length n.

Applying it, trade-offs and testing

Worked example: a cost roll-up service. A cloud billing system has an organisation tree of 200,000 accounts, folders and projects, and dashboards ask ‘spend under this folder’ thousands of times per second while usage events update leaf costs continuously. Flatten the tree once a minute, or on structural change, into tin/tout; keep a Fenwick tree of costs keyed by tin; apply each usage event as a point update; and answer roll-ups as range sums. Access checks of the form ‘may this user see this project?’ become ancestor tests against the folders the user is granted. Structural changes, such as moving a project, trigger a rebuild in the background and an atomic swap of the arrays; updates during the rebuild are replayed from a log.

Trade-offs. Compared with walking the subtree on every query, flattening costs O(n) memory for two integer arrays and a rebuild on structural change, and turns O(subtree size) queries into O(log n). Compared with storing a precomputed total at each node, it avoids O(depth) update propagation and supports arbitrary subtree aggregation. It loses to heavy-light decomposition for general path queries, and to dynamic trees when the shape changes often.

Testing. Generate random trees by attaching each new vertex to a random earlier one, shuffle adjacency lists, add path-shaped and star-shaped trees, and compare every operation against a brute-force walk. The code on this page passed that test on 400 random trees with 60 mixed operations each.

What to do next

1. Write the iterative euler_tin_tout and check on the example tree that tin = [0, 1, 4, 5, 2, 3, 6] and tout = [6, 3, 4, 6, 2, 3, 6].
2. Add the O(1) ancestor test and use it anywhere you currently walk parent pointers.
3. Pick the operation you need: subtree sum (Fenwick at tin), subtree add (difference at tin and tout + 1), path-to-root sum (+x/−x), or subtree min and max (segment tree).
4. Write a brute-force checker and run it on random, chain and star trees, including a single vertex.
5. Decide how structural changes are handled: rebuild and swap, or a dynamic-tree structure if moves are frequent.
6. If you need LCA, add the sparse table over the full walk or binary lifting, following the LCA guide.