Pattern Reference
Euler Tour (ETT)
"Flatten tree into array via Euler tour. Subtree queries become range queries. LCA via RMQ, subtree aggregates."
Loading...
Deep Dive Tutorial
The Euler tour trick flattens a tree into a linear array by recording the DFS visit order. Node v enters at time in[v] and leaves at time out[v]. Every node in v's subtree has entry time in [in[v], out[v]]. So "sum all values in subtree of v" = "range sum from in[v] to out[v]" on the flat array. Point update on a node = point update at its DFS position.
Euler tour preprocessing + subtree query
function eulerTour(n, edges, values, root = 0) {
const adj = Array.from({length: n}, () => []);
for (const [u, v] of edges) { adj[u].push(v); adj[v].push(u); }
const inTime = new Array(n);
const outTime = new Array(n);
const flat = new Array(n); // flat[i] = value of node with DFS order i
let timer = 0;
function dfs(u, parent) {
inTime[u] = timer;
flat[timer] = values[u];
timer++;
for (const v of adj[u]) {
if (v !== parent) dfs(v, u);
}
outTime[u] = timer - 1;
}
dfs(root, -1);
return { inTime, outTime, flat };
// Now: subtree of u = flat[inTime[u]..outTime[u]]
// Build segment tree / BIT on flat[] for range queries
}
// LCA via Euler tour (different variant — records every visit)
function eulerTourLCA(n, edges, root = 0) {
const adj = Array.from({length: n}, () => []);
for (const [u, v] of edges) { adj[u].push(v); adj[v].push(u); }
const euler = [], depth = new Array(n).fill(0), first = new Array(n);
let timer = 0;
function dfs(u, p, d) {
first[u] = timer;
euler[timer++] = [d, u];
depth[u] = d;
for (const v of adj[u]) {
if (v !== p) {
dfs(v, u, d + 1);
euler[timer++] = [d, u]; // record return
}
}
}
dfs(root, -1, 0);
// LCA(u,v) = min depth in euler[first[u]..first[v]]
// Use sparse table for O(1) RMQ after O(n log n) build
return { euler, first, depth };
}Worked Problems
map
Euler tour applications:
- Subtree range query: in[v]..out[v] on flat array
- LCA via RMQ: euler tour records every visit, LCA = minimum-depth node between first occurrences of u and v
- Re-rooting DP: combine in-time DFS with parent contributions
Subtree update trick: To add delta to all nodes in subtree of v, do point update +delta at in[v] and -delta at out[v]+1 on a difference array, then prefix sums give node values.
Implementation note: For LCA via Euler tour, the euler array has 2n-1 entries. Use sparse table on it for O(1) RMQ after O(n log n) build.
- Subtree range query: in[v]..out[v] on flat array
- LCA via RMQ: euler tour records every visit, LCA = minimum-depth node between first occurrences of u and v
- Re-rooting DP: combine in-time DFS with parent contributions
Subtree update trick: To add delta to all nodes in subtree of v, do point update +delta at in[v] and -delta at out[v]+1 on a difference array, then prefix sums give node values.
Implementation note: For LCA via Euler tour, the euler array has 2n-1 entries. Use sparse table on it for O(1) RMQ after O(n log n) build.