Euler Tour on Tree, in depth: the 2n-1 sequence, LCA as range minimum, and Euler tour trees for dynamic forests

Three things called an Euler tour

All three come from the same depth-first walk and differ only in what you record. Mixing them up is the commonest source of off-by-one errors: an array sized n for a 2n-1 sequence overflows on the first deep tree.

Building the 2n-1 sequence without recursion

Recursive DFS is the obvious way to produce the sequence and the wrong one for production. A path-shaped tree of a million nodes recurses a million deep, which overflows the default stack in C++ and Java and hits Python's recursion limit long before. Use an explicit stack that remembers, for each node, how far through its adjacency list it has got:

def euler_tour(n, adj, root=0):
    euler, first = [root], [-1] * n
    depth, parent, it = [0] * n, [-1] * n, [0] * n
    first[root] = 0
    stack = [root]
    while stack:
        u = stack[-1]
        if it[u] < len(adj[u]):
            v = adj[u][it[u]]
            it[u] += 1
            if v == parent[u]:
                continue
            parent[v], depth[v] = u, depth[u] + 1
            first[v] = len(euler)
            euler.append(v)                 # step down to v
            stack.append(v)
        else:
            stack.pop()
            if stack:
                euler.append(stack[-1])     # step back up to the parent
    return euler, first, depth, parent      # len(euler) == 2n - 1

Each node is pushed once and each adjacency entry is examined once, so the build is O(n). The first array, the index of each node's first appearance, is what LCA needs. Skipping the parent by comparing with parent[u] is safe for simple trees; with multi-edges you would skip by edge id instead.

Worked example

Take the tree with edges 0-1, 0-2, 1-3, 1-4, 2-5 and 4-6, rooted at 0. The walk gives the sequence 0, 1, 3, 1, 4, 6, 4, 1, 0, 2, 5, 2, 0, thirteen entries for seven nodes, matching 2n-1. The depths along it are 0, 1, 2, 1, 2, 3, 2, 1, 0, 1, 2, 1, 0. First appearances are 0 at index 0, 1 at 1, 3 at 2, 4 at 4, 6 at 5, 2 at 9 and 5 at 10.

To find lca(3, 6), look at indices 2 through 5: nodes 3, 1, 4, 6 at depths 2, 1, 2, 3. The shallowest is node 1, and node 1 is indeed the lowest common ancestor. For lca(6, 5) the window runs from index 5 to 10 and passes through the root at index 8, so the answer is 0. For lca(4, 6) the window is indices 4 to 5, nodes 4 and 6, and the answer is 4, the ancestor itself.

Why the shallowest node is the LCA

Why does the minimum-depth entry between the first visits always give the LCA? Let w be the LCA of u and v, and assume u is visited first. The walk reaches u inside the subtree of w and must reach v without leaving that subtree, because v is in it too. So every entry in the window is a node of w's subtree, and none is shallower than w.

The walk also passes through w itself. If u is w, the window starts at w. Otherwise u and v lie in different child subtrees of w, and to get from one to the other the walk must climb back up to w. So w appears in the window, it is the shallowest node that can, and the range minimum by depth returns it. Ties are impossible to get wrong, because the only node at that depth inside the window is w.

Constant-time LCA with a sparse table

With LCA reduced to range minimum over a static array, a sparse table answers each query in O(1). Row j stores the shallowest node in every window of length 2^j. Any query range is covered by two overlapping windows of the same power-of-two length, and overlapping is harmless for minimum:

def build_lca(euler, first, depth):
    m = len(euler)
    sp = [euler[:]]
    j = 1
    while (1 << j) <= m:
        prev, half = sp[-1], 1 << (j - 1)
        sp.append([a if depth[a] <= depth[b] else b
                   for a, b in zip(prev, prev[half:])])
        j += 1

    def lca(u, v):
        l, r = sorted((first[u], first[v]))
        j = (r - l + 1).bit_length() - 1
        a, b = sp[j][l], sp[j][r - (1 << j) + 1]
        return a if depth[a] <= depth[b] else b
    return lca

def dist(u, v, lca, depth):
    return depth[u] + depth[v] - 2 * depth[lca(u, v)]

Store node ids, not depths, in the table, and compare by depth; otherwise you get the depth of the LCA and not its identity. Testing this against a naive climb-the-parents LCA on 200 random trees with 50 queries each is a two-minute job that catches every indexing slip.

The table costs O(n log n) memory, which is about 21 rows for a million-node tree, or roughly 42 million integers. If that is too much, a segment tree over the same array uses O(n) memory and O(log n) queries. There is also an optimal O(n) build with O(1) queries that exploits the fact that adjacent depths differ by exactly one: split into blocks of about half log n, precompute every possible block shape, and use a sparse table over block minima. It is elegant and rarely worth the code. Binary lifting, covered in the LCA article, needs O(log n) per query but also answers k-th ancestor queries, which the tour cannot.

Euler tour trees: link, cut and reroot

Everything so far assumes the tree never changes. Suppose instead you have a forest whose edges are added and removed, and you must answer whether two nodes are connected, or how big a component is, between updates. Rebuilding the tour after each change costs O(n). An Euler tour tree avoids that by noticing what link and cut do to the tour as a sequence.

Use the edge-occurrence form: each node v contributes a self loop (v, v), and each tree edge contributes two directed occurrences, (u, v) going down and (v, u) coming back. A tree of s nodes has a tour of length 3s-2. Then three operations are sequence surgery. Rerooting at v rotates the sequence so it starts at v's self loop; a tour is cyclic, so any rotation is a valid tour. Linking u and v in different trees reroots both and concatenates them as tour(u), (u, v), tour(v), (v, u). Cutting the edge u-v finds its two occurrences and splits the sequence into three pieces: the middle piece is one tree, and the outer two pieces glued together are the other.

With a plain list each operation is O(n). Here is that reference model; it is the oracle you test the fast version against:

class EulerTourForest:                       # O(n) per operation; test oracle
    def __init__(self, n):
        self.tours = {v: [(v, v)] for v in range(n)}
        self.where = {v: v for v in range(n)}
        self.next_id = n

    def _reroot(self, v):
        tid = self.where[v]
        t = self.tours[tid]
        i = t.index((v, v))
        self.tours[tid] = t[i:] + t[:i]
        return tid

    def _store(self, seq):
        tid, self.next_id = self.next_id, self.next_id + 1
        self.tours[tid] = seq
        for a, _ in seq:
            self.where[a] = tid

    def connected(self, u, v):
        return self.where[u] == self.where[v]

    def link(self, u, v):
        tu, tv = self._reroot(u), self._reroot(v)
        seq = self.tours.pop(tu) + [(u, v)] + self.tours.pop(tv) + [(v, u)]
        self._store(seq)

    def cut(self, u, v):
        t = self.tours.pop(self.where[u])
        i, j = sorted((t.index((u, v)), t.index((v, u))))
        self._store(t[i + 1:j])
        self._store(t[:i] + t[j + 1:])

To make it fast, store each tour in a balanced binary search tree keyed implicitly by position, such as a treap or a splay tree, with a hash map from each occurrence to its BST node. Rotation is a split and a merge; link is three merges; cut is two splits and a merge; finding which tour holds a node is walking up to the BST root. Each is O(log n) expected or amortised. Store aggregates in the BST nodes, such as the count of self loops for component size or a sum of node values, and component queries come for free. The list model above matched a union-find recomputation across 200 random sequences of 200 link and cut operations, and the fast version should be tested the same way.

Where it is used, and where it is not

Euler tour trees are the building block of the fully dynamic connectivity algorithm of Holm, de Lichtenberg and Thorup, which maintains spanning forests at several levels with an ETT per level, and of earlier randomised work by Henzinger and King. They answer subtree and component questions well. They do not answer path questions, such as the maximum edge weight between two nodes, because a path is not contiguous in the tour; for that use link-cut trees, or heavy-light decomposition when the tree is static.

In engineering terms the static form appears wherever a hierarchy is queried far more often than it changes: org charts, file trees, category taxonomies, and phylogenetic or dependency trees in which you ask for common ancestors or distances in bulk. Build once, answer millions of LCA queries in constant time each.

Failure modes

• Wrong array sizes. The full sequence has 2n-1 entries and the edge form 3n-2 per tree; size for n and you overflow.
• Recursive DFS on deep trees. Stack overflow on path-shaped input; use the iterative build.
• Storing depths instead of nodes. The sparse table then returns the LCA depth, not the node.
• Mixing the two index spaces. Querying the 2n-1 sparse table with tin values from the n-length entry and exit form gives wrong windows. Any occurrence of each node works, but only in tour indices.
• Forgetting rerooting in ETT link. Concatenating unrotated tours produces a sequence that is not a valid walk.
• Disconnected input. A forest needs one tour per component, or a virtual root.

Trade-offs

For static trees with heavy query loads the tour plus sparse table is the fastest and simplest. If memory is tight, swap in a segment tree. If the forest changes and you only need connectivity or subtree aggregates, use an Euler tour tree; if you need path aggregates, use link-cut trees. The Cartesian tree connection runs the other way too: range minimum on any array reduces to LCA on its Cartesian tree, so the two problems are equivalent.

What to do next

1. Implement the iterative tour and check that its length is 2n-1 on random trees, including a path and a star.
2. Add the sparse table LCA and test it against a naive parent-climbing LCA on random queries.
3. Use it to compute tree distances and compare with BFS distances.
4. Implement the list-based Euler tour forest and test connected and size against union-find.
5. Replace the lists with an implicit treap and run the same randomised test against the list model.
6. Read the entry and exit time article for subtree sums, then link-cut trees for dynamic path queries.