Pattern Guide
Euler Tour (DFS Order)
"Flatten a tree into an array. Subtree queries become range queries."
An Euler tour (DFS order / in-time / out-time labeling) assigns each node an entry time and exit time during DFS. The key property: the subtree of node v occupies the contiguous range [in[v], out[v]] in the DFS order array. This converts subtree queries (sum of subtree, update subtree) into range queries on a flat array — solvable with a segment tree or Fenwick tree in O(log n).
Problems you can solve with this pattern
5 problems · click any to start solving
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 };
}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.
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 };
}- 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.