Euler Tour Tree

How the Euler tour technique works

Imagine running a DFS over a rooted tree and writing down every node the moment you enter it. The resulting sequence has length N (one entry per node) and a striking property: the subtree rooted at any vertex v occupies a contiguous range of positions. Why? Because DFS commits fully — once you step into v, you visit every descendant before backtracking past v's parent.

Concretely, record two integers per node: in[v] when the DFS first enters v, and out[v] when the DFS leaves it. The subtree of v covers exactly positions in[v] through out[v] in the tour. That's the key transformation: any subtree aggregate (sum, count, maximum) becomes a range aggregate over that interval, and a segment tree handles those in O(log N).

Worked example — 7-node tree

Consider the tree with root 1, children 2, 3, 4 of node 1, and node 2 has children 5, 6, 7:

         1
       / | \
      2  3  4
    / | \
   5  6  7

DFS starting at 1, visiting children in order: 1, 2, 5, 6, 7, 3, 4. Recording in[] and out[]:

Node	in[v]	out[v]	Subtree range
1	0	6	[0, 6] — whole tour
2	1	4	[1, 4] — nodes 2, 5, 6, 7
5	2	2	[2, 2] — just node 5
6	3	3	[3, 3] — just node 6
7	4	4	[4, 4] — just node 7
3	5	5	[5, 5] — just node 3
4	6	6	[6, 6] — just node 4

If each node stores a value and we want sum of subtree(2), query the segment tree over positions [1, 4]. If a value at node 6 changes, update position 3 in the segment tree. Both operations cost O(log N) — N = 7 here, so 3 comparisons. The DFS preprocessing is O(N) once.

Cost in real terms

Build phase: one DFS pass writes the tour array and in/out tables in O(N) time. Segment tree construction over the array is O(N). Each subsequent query — subtree sum, subtree max, subtree XOR, point update, or range update on a subtree — runs in O(log N) with the standard segment-tree machinery. On N = 1,000,000 nodes, a query touches ~20 segment-tree nodes — sub-microsecond on modern hardware.

Euler Tour Tree vs Heavy-Light Decomposition vs Link-Cut

	Euler Tour Tree	Heavy-Light Decomp	Link-Cut Tree	Centroid Decomposition
Subtree query	O(log N) ★	O(log² N)	O(log² N)	Complex
Path query (u → v)	Awkward	O(log² N) ★	O(log N) amortized	O(log² N)
Link / cut edges	O(log N) (Henzinger-King)	No (static)	O(log N) amortized ★	No (static)
Implementation	Easy	Medium	Hard	Hard
Memory	O(N)	O(N)	O(N)	O(N log N)
Typical use	Subtree aggregates	Path aggregates	Dynamic trees	Tree-DP / k-th distance

When to reach for the Euler tour

• Subtree-sum / subtree-min / subtree-count problems. Anything that asks "tell me an aggregate over all descendants of v" becomes a range query on the tour. Update one node, query any subtree — both O(log N).
• LCA queries with RMQ. Use the 2N-length Euler tour (each edge entered twice) paired with depths to find the lowest common ancestor of u and v via a range-minimum on the tour interval between their occurrences.
• Dynamic-tree connectivity (Euler-Tour-Tree as a data structure). Henzinger and King (1995) showed that storing the tour in a balanced BST supports link, cut, and connectivity queries in O(log N) each. Beats the simpler link-cut tree in some workloads.
• Persistent / version-control trees. Many incremental tree-algorithm libraries (folly, abseil, internal Git data structures) maintain Euler tours of object trees so that subtree-snapshot diffs become range diffs in a packed array.

JavaScript implementation

// Tree represented as adjacency list keyed by node id, rooted at `root`.
// values[v] is the value stored at vertex v.
class EulerTour {
  constructor(tree, root, values) {
    this.n = Object.keys(tree).length;
    this.in = new Map();
    this.out = new Map();
    this.tour = new Array(this.n); // tour[i] = value of node whose in-time is i
    this.nodeAt = new Array(this.n);
    let timer = 0;
    const stack = [[root, 0]];   // (node, childIndex)
    const parent = new Map(); parent.set(root, null);
    while (stack.length) {
      const top = stack[stack.length - 1];
      const [v, idx] = top;
      if (idx === 0) {
        this.in.set(v, timer);
        this.tour[timer] = values[v];
        this.nodeAt[timer] = v;
        timer++;
      }
      const children = (tree[v] || []).filter(c => c !== parent.get(v));
      if (idx < children.length) {
        const c = children[idx];
        parent.set(c, v);
        top[1]++;
        stack.push([c, 0]);
      } else {
        this.out.set(v, timer - 1);
        stack.pop();
      }
    }
    // Build segment tree on this.tour
    this.seg = new Array(4 * this.n).fill(0);
    this._build(1, 0, this.n - 1);
  }
  _build(node, l, r) {
    if (l === r) { this.seg[node] = this.tour[l]; return; }
    const m = (l + r) >> 1;
    this._build(node * 2, l, m);
    this._build(node * 2 + 1, m + 1, r);
    this.seg[node] = this.seg[node * 2] + this.seg[node * 2 + 1];
  }
  // Subtree-sum of vertex v
  subtreeSum(v) { return this._query(1, 0, this.n - 1, this.in.get(v), this.out.get(v)); }
  _query(node, l, r, ql, qr) {
    if (qr < l || r < ql) return 0;
    if (ql <= l && r <= qr) return this.seg[node];
    const m = (l + r) >> 1;
    return this._query(node * 2, l, m, ql, qr) + this._query(node * 2 + 1, m + 1, r, ql, qr);
  }
  // Point update: change vertex v's value to newValue
  update(v, newValue) { this._update(1, 0, this.n - 1, this.in.get(v), newValue); }
  _update(node, l, r, pos, val) {
    if (l === r) { this.seg[node] = val; return; }
    const m = (l + r) >> 1;
    pos <= m ? this._update(node * 2, l, m, pos, val) : this._update(node * 2 + 1, m + 1, r, pos, val);
    this.seg[node] = this.seg[node * 2] + this.seg[node * 2 + 1];
  }
}

// Example: 7-node tree
const tree = { 1:[2,3,4], 2:[1,5,6,7], 3:[1], 4:[1], 5:[2], 6:[2], 7:[2] };
const values = { 1:10, 2:5, 3:7, 4:3, 5:1, 6:2, 7:4 };
const ett = new EulerTour(tree, 1, values);
console.log(ett.subtreeSum(2));  // 5 + 1 + 2 + 4 = 12
ett.update(6, 100);
console.log(ett.subtreeSum(2));  // 5 + 1 + 100 + 4 = 110

Python implementation

class EulerTour:
    def __init__(self, tree, root, values):
        self.n = len(tree)
        self.tin, self.tout = {}, {}
        self.tour = [0] * self.n
        timer = 0
        # Iterative DFS to avoid recursion limit
        stack = [(root, iter(tree[root]), None)]
        self.tin[root] = 0; self.tour[0] = values[root]; timer = 1
        while stack:
            v, it, parent = stack[-1]
            try:
                c = next(it)
                while c == parent:
                    c = next(it)
                self.tin[c] = timer
                self.tour[timer] = values[c]
                timer += 1
                stack.append((c, iter(tree[c]), v))
            except StopIteration:
                self.tout[v] = timer - 1
                stack.pop()
        # Build Fenwick tree for sum queries
        self.bit = [0] * (self.n + 1)
        for i in range(self.n):
            self._add(i, self.tour[i])

    def _add(self, i, v):
        i += 1
        while i <= self.n: self.bit[i] += v; i += i & -i
    def _sum(self, i):
        s = 0; i += 1
        while i > 0: s += self.bit[i]; i -= i & -i
        return s

    def subtree_sum(self, v):
        return self._sum(self.tout[v]) - (self._sum(self.tin[v] - 1) if self.tin[v] > 0 else 0)
    def update(self, v, new_value):
        i = self.tin[v]; delta = new_value - self.tour[i]
        self.tour[i] = new_value; self._add(i, delta)

Variants and extensions

• Path-query Euler tour (LCA via RMQ). Visit each edge twice — once on descent, once on ascent — producing a 2N-length tour. Pair entries with node depth; LCA of u, v is the depth-minimum entry in the range between their first occurrences. With sparse-table RMQ, O(N log N) preprocessing then O(1) per LCA query.
• Euler-Tour-Tree as a balanced BST (Henzinger-King 1995). Store tour entries in a balanced BST keyed by position. Link(u, v) splices two BSTs together; cut(u, v) splits. Connectivity becomes "are u and v in the same BST?" — all in O(log N) worst-case. The basis for many dynamic-graph-connectivity algorithms.
• Lazy-propagation subtree updates. Standard segment-tree lazy propagation gives range-add-and-query on the tour. So adding a constant to every node in a subtree is O(log N) — useful for tree-DP problems where ancestors propagate gifts downward.
• Edge-based Euler tour. Some variants store edge weights instead of vertex values; the tour entries correspond to edges, and subtree-of-v aggregates all edges in the subtree.
• Mo's algorithm on the tour. Offline subtree queries can be answered with Mo's algorithm sorted by the tour; useful when the query aggregate doesn't fit a segment tree's structure (e.g., number of distinct values in a subtree).

Famous Euler-tour problems

Count distinct colors in subtree

Each node has a color. For each query "how many distinct colors appear in subtree(v)?" — flatten via Euler tour, then run Mo's algorithm sorted by [in[v], out[v]] intervals. Time: O((N + Q) √N). The CSES "Distinct Colors" problem and the Codeforces problem 600E (Lomsat gelral) both reduce to this pattern. The naive O(N²) brute force times out around N = 10⁵; the Euler-tour + offline approach finishes in seconds.

Online tree rerooting

"Given a tree, for each i, output the sum of values in subtree(i) when the tree is rerooted at i." The Euler tour from root 1 gives subtree sums for that rooting. To convert to subtree(i) under root i, use the identity: subtree(i, root=i) = total_sum − subtree(parent(i), root=1) + subtree(i, root=1). Two queries per output — still O(log N) each.

Common bugs and edge cases

• Off-by-one in out[v]. Decide whether out[v] is the last tour position inside subtree(v) (inclusive — most common) or the first position outside (exclusive). Mixing conventions silently corrupts every range query.
• Wrong DFS order across runs. If children are iterated in a different order between the tour build and a later update, the in/out indices still match (the maps are persistent), but the range bounds for subtrees depend on the build-time order — never recompute partially.
• Stack overflow on deep trees. A chain of 10⁶ nodes blows JavaScript's recursion limit at ~10⁴. Always implement DFS iteratively with an explicit work stack for production-grade ETT.
• Forgetting the segment tree. The Euler tour is just a numbering — without a range-aggregate data structure on top, subtree queries are still O(N). The whole point is the layering.
• Path queries on subtree tour. The N-length entry-only tour does not give path ranges. Either use the 2N variant for LCA / RMQ, or switch to Heavy-Light Decomposition for direct path aggregates.
• Mutating the tree structure after build. The classical Euler tour assumes a static tree. If edges change, rebuild — or use the dynamic Euler-Tour-Tree (balanced BST) variant for online link/cut.