Euler Tour Tree

Euler tour tree (ETT) is a dynamic graph data structure within computation and algorithms introduced by Monika R. Henzinger and Valerie King in 1995 (building on Robert E. Tarjan and Uzi Vishkin's 1984 parallel Euler tour technique) to maintain a dynamic forest of unrooted trees under edge insertions (link), edge deletions (cut), tree rerooting, connected-component queries, and subtree aggregate queries in O(log n) time per operation. Whereas Daniel Sleator and Robert E. Tarjan's 1983 link-cut tree decomposes a tree into vertex-disjoint preferred paths and excels at aggregating weights along a root-to-vertex path, an Euler tour tree linearizes the entire two-dimensional topology of each tree into a single one-dimensional sequence by recording its depth-first Euler tour, and stores that sequence inside a self-balancing binary search tree such as a red-black tree, AVL tree, treap, or splay tree.

Because every subtree of a rooted tree corresponds to a single contiguous interval of the Euler tour sequence, while inserting or deleting a tree edge splices or excises at most two contiguous intervals of the tour, all topological updates and whole-subtree associative aggregations reduce directly to O(log n) sequence split and join (concatenation) operations. In computational complexity theory and algorithm engineering, Euler tour trees serve as the backbone of randomized and deterministic dynamic connectivity algorithms (including the Holm-de Lichtenberg-Thorup O(log² n) polylogarithmic dynamic graph connectivity structure) and dynamic minimum spanning tree maintenance.

Let T = (V, E) be an unrooted tree on n = |V| vertices and n − 1 undirected edges. To linearize T into a cycle, replace each undirected edge {u, v} ∈ E with two oppositely directed arcs (u, v) and (v, u). In the resulting directed multigraph D(T), every vertex v ∈ V has in-degree equal to out-degree (deg⁻(v) = deg⁺(v) = deg(v)), so D(T) is Eulerian and admits a directed Euler tour that traverses every directed arc (u, v) once before returning to the starting vertex r.

Two closely related linear encodings of the Euler tour are used in practice:

1. Vertex-Visit Sequence (2n − 1 Entries): Starting a depth-first traversal at root r, record each vertex every time the walk visits it (upon initial entry and upon returning from each child subtree). Because the walk starts at r and takes 2(n − 1) directed steps, the vertex-visit sequence ET(T) has length 2n − 1, in which each vertex v appears deg(v) times (except the root r, which appears deg(r) + 1 times).
2. Directed-Arc Sequence (2n − 2 Arcs + n Self-Loops): Alternatively, store only the 2n − 2 directed arcs (u, v) in their Euler traversal order, augmented by a canonical self-loop arc (v, v) at the first visit to each vertex v ∈ V so that vertex weights and isolated single-vertex trees (n = 1, 0 edges) have a dedicated node of length 3n − 2.

To distinguish the single canonical representative of a vertex v from its secondary revisit appearances when computing subtree sums or sizes, only the first occurrence first(v) (or the self-loop node (v, v)) holds the active vertex weight w(v), while all secondary occurrences of v store the monoid identity element 0. Each vertex v maintains direct pointers to its first and last occurrences (first(v) and last(v)), and each undirected edge e = {u, v} maintains direct pointers to the two tree nodes representing its directed arcs (u, v) and (v, u).

Each tree's Euler tour sequence is stored as the in-order traversal of a balanced binary search tree (such as a weight-balanced treap, splay tree, red-black tree, or 2–3 finger tree) equipped with parent pointers, where keys are implicit sequence positions rather than explicit numbers. The balanced BST supports two fundamental primitives in O(log n) time:

• Split(S, x): Partitions the sequence S at node x into (S_left, S_right), where S_left contains all elements preceding x and S_right begins with x.
• Join(S₁, S₂): Concatenates two sequences S₁ and S₂ into a single balanced BST S₁ · S₂.

Using only Split, Join, and upward root traversal, an Euler tour tree implements all dynamic forest primitives in O(log n) time:

1. Connected-Component Queries: FindRoot(v) and Connected(u, v)

To determine whether two vertices u and v belong to the same connected component of the forest, start at node first(u) and node first(v) in the balanced BST and follow parent pointers up to their respective BST roots in O(log n) time. Because each connected component is represented by a single BST, u and v are connected in the forest if and only if their BST roots are identical. Unlike a disjoint-set data structure, which achieves O(α(n)) amortized time for insertion-only connectivity, the Euler tour tree maintains full connectivity under arbitrary interleaved edge deletions.

2. Rerooting a Tree: Reroot(T, r)

Changing the designated root of tree T from its current root r₀ to a new vertex r corresponds to a cyclic shift of the Euler tour cycle so that the tour begins and ends at r. In the vertex-visit representation (where the trailing duplicate of r₀ is dropped when viewing the tour as a circular cycle of 2n − 2 steps), splitting the sequence just before first(r) into (A, B), swapping the two halves into B · A, and appending a new closing visit to r executes via two Split and two Join calls in O(log n) time.

3. Deleting an Edge: Cut(u, v)

When an undirected edge e = {u, v} (with u closer to the root than v) is deleted, the directed arc (u, v) marks the entry into v's subtree T_v, and the reverse directed arc (v, u) marks the exit from T_v back to u. Consequently, the original Euler tour S decomposes into three contiguous segments positioned around the two arcs (u, v) and (v, u):

S = J · [(u, v)] · K · [(v, u)] · L,

where the middle segment K is the complete, self-contained Euler tour of the child subtree T_v, and the outer concatenation J · L (merging the two occurrences of u on either side of the excised excursion) is the valid Euler tour of the remaining tree T \ T_v. Performing two Split operations at (u, v) and (v, u) to excise K and one Join operation to weld J and L back together completes Cut(u, v) in O(log n) time.

4. Inserting an Edge: Link(u, v)

To add an undirected edge e = {u, v} connecting two vertices u and v in distinct trees T_u and T_v (verified first via Connected(u, v) = false), first execute Reroot(T_v, v) so that the Euler tour K of T_v starts and ends at v. Next, split the Euler tour of T_u right after an occurrence of u into (J, L), and join the pieces with the two newly allocated directed arcs (u, v) and (v, u):

S_new = J · [(u, v)] · K · [(v, u)] · L.

This requires one reroot, one Split, and three Join calls, running in O(log n) time.

The primary algorithmic advantage of an Euler tour tree over a standard link-cut tree is its native support for non-invertible subtree aggregations (such as computing the minimum or maximum vertex weight in a subtree T_v, or applying a lazy range addition to all vertices in T_v, analogous to a segment tree or Fenwick tree).

In a link-cut tree, a vertex v can have arbitrarily many "light" (dashed) children whose subtrees are not part of v's preferred splay path; maintaining the minimum over all light children requires either an invertible operation (such as addition, where subtracting a detached child's sum takes O(1) time) or storing an auxiliary balanced heap at every vertex. In an Euler tour tree, by contrast, the entire subtree T_v rooted at v (when u is v's parent) is precisely the contiguous subsegment K bounded between the directed arc (u, v) and the reverse arc (v, u). Consequently, augmenting each BST node with the associative monoid aggregate of its BST subtree—exactly as in a segment tree—allows querying the sum, minimum, maximum, or count of any subtree T_v (or applying a lazy tag to T_v) by temporarily splitting out K (or querying the interval between (u, v) and (v, u)) in O(log n) time.

In Monika Henzinger and Valerie King's 1995 randomized dynamic connectivity algorithm and Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup's 2001 deterministic O(log² n) amortized dynamic connectivity structure (the HDT algorithm), a general undirected graph G = (V, E) undergoing arbitrary edge insertions and deletions is maintained via a hierarchy of ⌊log₂ n⌋ + 1 spanning forests F₀ ⊇ F₁ ⊇ ... ⊇ F_L, where each forest F_i is represented as an Euler tour tree:

• Every tree edge e and non-tree edge has a level ℓ(e) ∈ [0, L] satisfying the invariant that any connected component at level i has at most ⌊n / 2ⁱ⌋ vertices.
• When a spanning-tree edge e = {u, v} is deleted, Cut(u, v) splits its component into T_u and T_v across levels 0 through ℓ(e). To determine whether G remains connected, the algorithm must locate a replacement non-tree edge joining T_u and T_v.
• Because each Euler tour tree node is augmented with the count of incident level-i non-tree edges in its subtree (a subtree aggregate), the HDT algorithm identifies the smaller subtree (say |T_u| ≤ |T_v|), traverses only the BST subtrees of T_u that have a non-zero count of incident level-i edges in O(log n) time per candidate edge, promotes inspected non-tree edges that fail to cross the cut to level i + 1 (at most log₂ n promotions per edge over its lifetime), and reconnects the Euler tour trees in O(log² n) amortized time.

Why can an Euler tour tree not directly compute path minimums between two vertices u and v?

In the Euler tour sequence of a tree, walking from u to v traverses not only the simple path between u and v, but also detours completely into and out of every intermediate sibling subtree hanging off that path. For an invertible group operation such as addition or XOR, one can store +w(x) at first(x) and −w(x) at last(x) so that any completely traversed off-path subtree cancels to zero (+w(x) − w(x) = 0). However, for a non-invertible semigroup operation such as min or max, off-path subtree excursions cannot be canceled out of the prefix interval, requiring a link-cut tree or top tree instead.

How many BST nodes are required to represent a forest of n vertices in an Euler tour tree?

In the directed-arc plus vertex-self-loop representation, each of the n vertices contributes 1 self-loop node (v, v) and each of the at most n − 1 undirected forest edges contributes 2 directed arc nodes (u, v) and (v, u), requiring at most n + 2(n − 1) = 3n − 2 BST nodes in total. All n vertex nodes can be pre-allocated in a static array, and the 2(n − 1) arc nodes can be drawn from a fixed-size pool in O(n) total memory.

1. Tarjan, R. E., & Vishkin, U. (1985). "An efficient parallel biconnectivity algorithm." SIAM Journal on Computing, 14(4), 862–874. https://doi.org/10.1137/0214061
2. Henzinger, M. R., & King, V. (1999). "Randomized fully dynamic graph algorithms with polylogarithmic time per operation." Journal of the ACM, 46(4), 502–516 (Preliminary version in STOC 1995, 519–527). https://doi.org/10.1145/320211.320215
3. Holm, J., de Lichtenberg, K., & Thorup, M. (2001). "Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity." Journal of the ACM, 48(4), 723–760. https://doi.org/10.1145/502090.502095
4. Sleator, D. D., & Tarjan, R. E. (1983). "A data structure for dynamic trees." Journal of Computer and System Sciences, 26(3), 362–391. https://doi.org/10.1016/0022-0000(83)90006-590006-5)
5. Wulff-Nilsen, C. (2013). "Faster deterministic fully-dynamic graph connectivity." Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1757–1769. https://doi.org/10.1137/1.9781611973105.126