Skip to content

Euler Tour and DFS Ordering

Platform Connection — Curve Flattening: In our Array course, you learned to see arrays as 1D curves and apply prefix sums, difference arrays, and sliding windows. A tree is a branching, non-linear space where those tools don't work — until now. The Euler Tour takes a tree and physically crushes it flat into a 1D array. Once flattened, "sum of subtree of \(v\)" becomes a range sum on a contiguous segment. Every weapon from the Array course works again. Linearization is the bridge from trees back to curves.

Euler tour assigns entry and exit times, flattening the tree into an array

The Problem with Trees

You're given a rooted tree with \(n\) nodes and you need to answer questions like "is node \(u\) an ancestor of node \(v\)?" The obvious approach: start at \(v\) and walk up to the root, checking if you hit \(u\). That's \(O(n)\) per query. If you have \(10^5\) queries on a tree with \(10^5\) nodes, that's \(10^{10}\) operations. Way too slow.

What if you could answer "is \(u\) an ancestor of \(v\)?" in \(O(1)\)?

The trick is to stop thinking of the tree as a tree. Flatten it into an array. Once it's an array, you have decades of powerful data structure tools at your disposal.

Entry and Exit Times

Run a DFS from the root. Keep a global timer. When you first visit a node, record its entry time (\(tin\)). When you finish processing all its children and backtrack, record its exit time (\(tout\)). Increment the timer at each event.

The Insight: Node \(u\) is an ancestor of node \(v\) if and only if \(tin[u] \leq tin[v]\) and \(tout[v] \leq tout[u]\).

Why does this work? If \(u\) is an ancestor of \(v\), the DFS enters \(u\) before it enters \(v\) (so \(tin[u] \leq tin[v]\)), and it exits \(v\) before it exits \(u\) (so \(tout[v] \leq tout[u]\)). The interval \([tin[v], tout[v]]\) is completely contained inside \([tin[u], tout[u]]\).

If \(u\) is NOT an ancestor of \(v\), the intervals are either disjoint (different subtrees) or \(v\)'s interval contains \(u\)'s (meaning \(v\) is the ancestor, not \(u\)).

Ancestor check becomes a range containment check. Two comparisons. \(O(1)\).

Trace on a 7-Node Tree

Consider this tree rooted at node 1:

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

We run DFS. Children are visited in order (2, 3, 4 for node 1; 5, 6 for node 2; 7 for node 4).

Event Node Action Timer
1 1 enter tin[1] = 0
2 2 enter tin[2] = 1
3 5 enter tin[5] = 2
4 5 exit tout[5] = 3
5 6 enter tin[6] = 4
6 6 exit tout[6] = 5
7 2 exit tout[2] = 6
8 3 enter tin[3] = 7
9 3 exit tout[3] = 8
10 4 enter tin[4] = 9
11 7 enter tin[7] = 10
12 7 exit tout[7] = 11
13 4 exit tout[4] = 12
14 1 exit tout[1] = 13

Summary:

Node tin tout
1 0 13
2 1 6
3 7 8
4 9 12
5 2 3
6 4 5
7 10 11

Verifying the Ancestor Property

Is 1 an ancestor of 7? \(tin[1] = 0 \leq 10 = tin[7]\) and \(tout[7] = 11 \leq 13 = tout[1]\). Yes.

Is 2 an ancestor of 7? \(tin[2] = 1 \leq 10 = tin[7]\) but \(tout[7] = 11 > 6 = tout[2]\). No. Correct — node 7 is in node 4's subtree, not node 2's.

Is 4 an ancestor of 7? \(tin[4] = 9 \leq 10 = tin[7]\) and \(tout[7] = 11 \leq 12 = tout[4]\). Yes.

Is 5 an ancestor of 6? \(tin[5] = 2 \leq 4 = tin[6]\) but \(tout[6] = 5 > 3 = tout[5]\). No. They're siblings.

Every check is two comparisons. No traversal needed.

The Flat Array: DFS Ordering

Now look at the nodes sorted by \(tin\):

Position 0 1 2 3 4 5 6
Node 1 2 5 6 3 4 7

This is the DFS ordering — nodes listed in the order they were first visited. Here's the key property:

Every subtree is a contiguous segment in this array.

The subtree of node 2 contains nodes {2, 5, 6}. In the DFS ordering, they occupy positions 1, 2, 3 — a contiguous block. The subtree of node 4 contains {4, 7}, occupying positions 5, 6 — contiguous again.

In general, the subtree of node \(v\) occupies positions \([tin[v], tout[v]]\) in the DFS ordering (using the convention where \(tin\) increments only on entry, giving each node a unique position). We'll use this property heavily in the next lesson to turn subtree queries into range queries.

The Code

int timer = 0;
vector<int> adjacency[200005];
int entryTime[200005], exitTime[200005];

void dfs(int node, int parent) {
    entryTime[node] = timer++;
    for (int child : adjacency[node]) {
        if (child != parent) {
            dfs(child, node);
        }
    }
    exitTime[node] = timer++;
}

bool isAncestor(int u, int v) {
    return entryTime[u] <= entryTime[v] && exitTime[v] <= exitTime[u];
}

Complexity: \(O(n)\) preprocessing, \(O(1)\) per ancestor query.

Note: for very deep trees (\(n > 10^5\)), the recursive DFS might stack overflow. In competitive programming, you'd use an iterative DFS or increase the stack size. For the trees we'll see in this course, recursion is fine.

Why This Matters

This lesson introduced the fundamental idea behind all of Chapter 11: a tree can be flattened into an array, and tree relationships become array relationships.

  • Ancestor check becomes range containment: \(O(1)\).
  • Subtree becomes contiguous segment — opening the door to range query data structures.
  • Path queries (next lesson after subtree queries) use a variation called the Euler tour.

You'll never look at a tree the same way again. When someone says "subtree query," your reflex should be: flatten, then use an array tool.

Try It

The starter code builds a tree and runs DFS. Fill in the dfs function to compute entryTime and exitTime.

Predict before running: On a tree that's a straight chain 1 → 2 → 3 → 4, what are the entry/exit times? Node 1 gets \(tin=0\). Node 2 gets \(tin=1\). Node 3 gets \(tin=2\). Node 4 gets \(tin=3, tout=4\). Then we backtrack: \(tout[3]=5, tout[2]=6, tout[1]=7\).

Challenge: If two nodes \(u\) and \(v\) have disjoint intervals (neither contains the other), what is their relationship in the tree? They're in different subtrees — neither is an ancestor of the other.

Edge Cases to Watch For

  • isAncestor(u, u) — node is its own ancestor: The containment check \(tin[u] \le tin[v]\) AND \(tout[v] \le tout[u]\) must use <= (not <) for the self-ancestor case to return true. Using strict inequality breaks this.

Problems

Problem Link Difficulty
CSES — Subordinates cses.fi/problemset/task/1674 Easy
CSES — Company Queries I cses.fi/problemset/task/1687 Medium
CF 208E — Blood Cousins codeforces.com/problemset/problem/208/E Hard