---
title: "Entry/Exit Times and the Euler Tour"
summary: Flatten a tree into an array, and get subtree queries, ancestry tests and LCA-from-RMQ for free.
difficulty: core
tags: [trees, flatten, RMQ]
time: n
space: n
prereq: [trees/dfs]
see: [lca/rmq-lca, structures/segment-tree, advanced-tree/hld]
---

There are two different objects with this name, and mixing them up ruins afternoons:

:::definition label="Two tours"
- **Tin/tout (entry–exit, DFS order)**: $\operatorname{tin}[u]$ when $u$ is first visited, $\operatorname{tout}[u]$ after its whole subtree is done. Subtree of $u$ = the *contiguous* interval $[\operatorname{tin}[u], \operatorname{tout}[u])$.
- **Euler tour of the walk** (also called the *first-occurrence* tour): the length-$2n-1$ sequence of vertices visited along the DFS walk, including repeats when returning up. Its range minima give LCA.
:::

```cpp tin-tout.cpp
vector<int> tin(n), tout(n), flat(n);      // flat[tin[u]] = u
int timer = 0;
void dfs(int u, int p) {
    tin[u] = timer; flat[timer] = u; timer++;
    for (int v : g[u]) if (v != p) dfs(v, u);
    tout[u] = timer;                       // half-open: [tin, tout)
}
bool is_ancestor(int u, int v) { return tin[u] <= tin[v] && tout[v] <= tout[u]; }
```

:::theorem title="Subtree = interval"
$v$ lies in the subtree of $u \iff \operatorname{tin}[u] \le \operatorname{tin}[v] < \operatorname{tout}[u] \iff [\operatorname{tin}[v], \operatorname{tout}[v]) \subseteq [\operatorname{tin}[u], \operatorname{tout}[u])$.
:::

:::proof
DFS enters $u$, then recursively finishes each child's entire subtree before exiting $u$; so all times assigned between $\operatorname{tin}[u]$ and $\operatorname{tout}[u]$ belong to descendants, and nothing outside that window can be a descendant. ∎
:::

## Everything this buys
:::example title="Subtree add / subtree sum"
Add $x$ to every vertex in the subtree of $u$; query the value at $v$: one range-add/point-query @structures/fenwick over the flat array. Subtree sum? Range-sum over $[\operatorname{tin}[u], \operatorname{tout}[u])$. Both $O(\log n)$.
:::

```cpp subtree-queries.cpp
// subtree add, subtree sum:  BIT with two arrays (standard trick) or a lazy segtree
bit1.add(tin[u], x);      bit1.add(tout[u], -x);            // point query at v:
val = bit1.sum(tin[v]);
// sum over a subtree needs the "weighted" version:
add(l, r, x):  bitA.add(l, x); bitA.add(r, -x);
              bitB.add(l, x*(l-1)); bitB.add(r, -x*r);
prefix(p) = p*sum(bitA, p) - sum(bitB, p);
```

:::note title="Which to use, honestly"
If updates are on *vertices/edges* and queries are subtree-aggregate, tin/tout + a lazy segment tree is the shortest correct code. The moment queries involve *paths* (root-to-vertex, $u$–$v$), tin/tout alone is not enough: jump to @advanced-tree/hld (paths split into $O(\log n)$ subtree-queries) or Euler-tour + LCA for root-paths only.
:::

## The 2n−1 tour and RMQ
Walk the tree along the DFS, appending a vertex each time you step onto it (down *or* up). Length $2n-1$. Then:

:::theorem title="LCA ⟺ RMQ"
$\operatorname{lca}(u,v)$ is the vertex of minimum depth in the tour between the first occurrences of $u$ and $v$.
:::

:::proof
Between the first visit of $u$ and the first visit of $v$ the walk must leave $u$'s branch and climb to their common ancestor; it cannot climb above $\operatorname{lca}(u,v)$ without having visited that ancestor later (which would place a shallower vertex inside the interval, and contradict that both are still below it). The vertex where the walk turns around is exactly $\operatorname{lca}(u,v)$, and it is the unique shallowest one in the range. ∎
:::

So "LCA in $O(1)$" reduces to "RMQ in $O(1)$ after $O(n \log n)$", solved by a sparse table (@structures/sparse-table) — or $O(n)$ build with the ±1 RMQ trick (@lca/rmq-lca).

```cpp euler-2n1.cpp
vector<int> tour, first(n, -1), depth(n);
void dfs(int u, int p, int d) {
    first[u] = (int)tour.size(); tour.push_back(u); depth[u] = d;
    for (int v : g[u]) if (v != p) {
        dfs(v, u, d + 1);
        tour.push_back(u);                     // coming back up
    }
}
int lca(int u, int v) {
    int l = first[u], r = first[v]; if (l > r) swap(l, r);
    return rmq_min_by_depth(l, r);             // sparse table over tour[]
}
```

:::trap title="tout[u] = timer++ is a bug, not a style choice"
Some references define `tout` as a third increment ("timer used 2n times"). Then subtree = $[\operatorname{tin}[u], \operatorname{tout}[u]]$ *inclusive*, and the interval test changes to `tin[u] <= tin[v] && tout[u] >= tout[v]`. Pick one convention and write it as a comment in your template — mixed conventions between a `is_ancestor` helper and a segment tree is a classic 20-minute penalty.
:::

:::figure src="Simple_Rooted_Tree.svg" caption="The DFS walk down-and-up: 2n−1 entries, first occurrences marked, and the subtree of each vertex as one contiguous block."
:::

:::problems
- [[CSES 1137]] Subtree Queries | https://cses.fi/problemset/task/1137 | core | tin/tout + segtree
- [[CSES 1674]] Subordinates | https://cses.fi/problemset/task/1674 | easy | subtree sizes
- [[CF 339D]] Xenia and Bit Operations | https://codeforces.com/problemset/problem/339/D | core | tree-as-segtree
:::