# Euler Tour Technique

Authors: Benjamin Qi, Andrew Wang, Neo Wang

Flattening a tree into an array to easily query and update subtrees.

## Introduction

Focus Problem – try your best to solve this problem before continuing!

If we can preprocess a rooted tree such that every subtree corresponds to a contiguous range on an array, we can do updates and range queries on it!

### Tutorial

Resources | ||||
---|---|---|---|---|

CPH | introduces tree traversal array, how to solve above problem | |||

SecondThread |

### Implementation

Let's use the below graph for a quick demo of the technique:

Here's the code we're going to use to perform a Euler Tour on the graph. Notice that it follows the same general structure as a normal depth-first search. It's just that in this algorithm, we're keeping a few auxiliary variables we're going to use later on.

C++

#include <iostream>#include <vector>using std::vector;// The graph represented as an adjacency list (0-indexed)vector<vector<int>> neighbors{{1, 2}, {0}, {0, 3, 4}, {2}, {2}};vector<int> start(neighbors.size());vector<int> end(neighbors.size());int timer = 0;

Java

public class EulerTour {// The graph represented as an adjacency list (0-indexed)static int[][] neighbors = new int[][] {{1, 2}, {0}, {0, 3, 4}, {2}, {2}};static int[] start = new int[neighbors.length];static int[] end = new int[neighbors.length];static int timer = 0;static void eulerTour(int at, int prev) {start[at] = timer++;for (int n : neighbors[at]) {if (n != prev) { eulerTour(n, at); }}end[at] = timer;}}

Python

# The graph represented as an adjacency list (0-indexed)neighbors = [[1, 2], [0], [0, 3, 4], [2], [2]]start = [0] * len(neighbors)end = [0] * len(neighbors)timer = 0def euler_tour(at: int, prev: int):global timerstart[at] = timertimer += 1for n in neighbors[at]:if n != prev:euler_tour(n, at)end[at] = timer

### Tour Walkthrough

Before the tour, our $\texttt{start}$ and $\texttt{end}$ arrays are initialized with zeros. In this visualization, the first row represents the node indices, the second row represents $\texttt{start}$, and the third represents $\texttt{end}$.

For brevity's sake, in this walkthrough, we're going to use $\text{dfs}$ instead of the full above function name.

**Current timer value: 0**

Node Index | 1 | 2 | 3 | 4 | 5 |

$\texttt{start}$ | 0 | 0 | 0 | 0 | 0 |

$\texttt{end}$ | 0 | 0 | 0 | 0 | 0 |

Since we call $\text{dfs}(1, 0)$, we set $\texttt{start}[1]$ to the current timer value of $0$. Then, we proceed to call $\text{dfs}(2, 1)$ and $\text{dfs}(3, 1)$.

**Current timer value: 1**

Node Index | 1 | 2 | 3 | 4 | 5 |

$\texttt{start}$ | 0 | 0 | 0 | 0 | 0 |

$\texttt{end}$ | 0 | 0 | 0 | 0 | 0 |

Now we must resolve $\text{dfs}(2, 1)$ and $\text{dfs}(3, 1)$. It does not matter which order we process these in, so for this example, we start with $\text{dfs}(2, 1)$. Since the timer value is 1, we set $\texttt{start}[2]$ to 1 and increment the timer. However, because node $2$ has no children, we don't call $\text{dfs}$. Instead, we set $\texttt{end}[2]$ to 2 because our current timer is now 2.

**Current timer value: 2**

Node Index | 1 | 2 | 3 | 4 | 5 |

$\texttt{start}$ | 0 | 1 | 0 | 0 | 0 |

$\texttt{end}$ | 0 | 2 | 0 | 0 | 0 |

Now we must resolve $\text{dfs}(3, 1)$. Similar to before, we set $\texttt{start}[3]$ to the value of the timer (2 in this case) and increment the timer. Then, we proceed to make the calls $\text{dfs}(4, 3)$ and $\text{dfs}(5, 3)$.

**Current timer value: 3**

Node Index | 1 | 2 | 3 | 4 | 5 |

$\texttt{start}$ | 0 | 1 | 2 | 0 | 0 |

$\texttt{end}$ | 0 | 2 | 0 | 0 | 0 |

Now we must resolve $\text{dfs}(4, 3)$ and $\text{dfs}(5, 3)$. First, we resolve $\text{dfs}(4, 3)$ by setting $\texttt{start}[4]$ to the value of the timer (3 in this case) and incrementing the timer. Then, since node $4$ has no children, set $\texttt{end}[4]$ to 4.

Now the value of the timer is 4, and we must resolve $\text{dfs}(5, 3)$. Similar to before, we set $\texttt{start}[5]$ to 4. Since node $5$ also has no children, set $\texttt{end}[5]$ to 5.

**Current timer value: 5**

Node Index | 1 | 2 | 3 | 4 | 5 |

$\texttt{start}$ | 0 | 1 | 2 | 3 | 4 |

$\texttt{end}$ | 0 | 2 | 0 | 4 | 5 |

Now, we must resolve the remaining $\texttt{end}[\text{node}] = \text{timer}$ calls. We first encounter and resolve node $3$, setting $\texttt{end}[3]$ to 5. We then do the same for node $1$, setting $\texttt{end}[1]$ to 5. Our DFS traversal is now complete.

Node Index | 1 | 2 | 3 | 4 | 5 |

$\texttt{start}$ | 0 | 1 | 2 | 3 | 4 |

$\texttt{end}$ | 5 | 2 | 5 | 4 | 5 |

Notice that after running $\text{dfs}$, each range $[\texttt{start}[i], \texttt{end}[i]]$ contains all ranges $[\texttt{start}[j], \texttt{end}[j]]$ for each $j$ in the subtree of $i$. Also, $\texttt{end}[i]-\texttt{start}[i]$ is equal to the subtree size of $i$.

Here's a small animation of the tour if you're still confused:

### Solution - Subtree Queries

C++

#include <algorithm>#include <iostream>#include <vector>using std::cout;using std::endl;using std::vector;Code Snippet: BIT (from PURS module) (Click to expand)

## LCA

Focus Problem – try your best to solve this problem before continuing!

Focus Problem – try your best to solve this problem before continuing!

### Tutorial

Resources | ||||
---|---|---|---|---|

CPH | ||||

cp-algo |

### Implementation

Resources | ||||
---|---|---|---|---|

Benq |

C++

int n; // The number of nodes in the graphvector<int> graph[100000];int timer = 0, tin[100000], euler_tour[200000];int segtree[800000]; // Segment tree for RMQvoid dfs(int node = 0, int parent = -1) {tin[node] = timer; // The time when we first visit a nodeeuler_tour[timer++] = node;for (int i : graph[node]) {if (i != parent) {

Java

import java.io.*;import java.util.*;public class LCA {public static int[] euler_tour, tin;public static int timer, size, N;public static ArrayList<Integer> g[];// Segtree codepublic static final int maxsize = (int)1e7; // limit for array size

## Sparse Tables

The above code does $\mathcal{O}(N)$ time preprocessing and allows LCA queries
in $\mathcal{O}(\log N)$ time. If we replace the segment tree that computes
minimums with a **sparse table**, then we do $\mathcal{O}(N\log N)$ time
preprocessing and query in $\mathcal{O}(1)$ time.

Focus Problem – try your best to solve this problem before continuing!

The following is an example implementation of a sparse table and code that answers LCA queries. Build time is $\mathcal{O}(N\log N)$, and queries are $\mathcal{O}(1)$.

C++

#include <bits/stdc++.h>using namespace std;template <typename T> class SparseTable {private:int n, log2dist;vector<vector<T>> st;public:SparseTable(const vector<T> &v) {

### Resources

Resources | ||||
---|---|---|---|---|

CPH | diagrams | |||

PAPS | code | |||

cp-algo |

### Optional: Faster Preprocessing

From CPH:

There are also more sophisticated techniques where the preprocessing time is only $\mathcal{O}(N)$, but such algorithms are not needed in competitive programming.

Ex. the following:

### Implementation

C++

Resources | ||||
---|---|---|---|---|

Benq |

## Problems

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

CSES | Easy | ## Show TagsEuler Tour, PURS | |||

CSES | Normal | ## Show TagsEuler Tour, PURS | |||

Gold | Normal | ## Show TagsEuler Tour, HLD, PURS | |||

Gold | Normal | ## Show TagsEuler Tour, LCA | |||

Platinum | Normal | ## Show TagsEuler Tour, PURS | |||

AC | Normal | ## Show TagsEuler Tour | |||

CF | Normal | ## Show TagsEuler Tour | |||

AC | Normal | ## Show TagsBinary Search, Euler Tour | |||

AC | Hard | ## Show TagsLCA, PURS | |||

IOI | Hard | ## Show TagsBinary Search, Euler Tour | |||

Platinum | Hard | ## Show TagsEuler Tour, Lazy SegTree, PURS | |||

CF | Hard | ## Show TagsEuler Tour, RURQ | |||

DMOPC | Very Hard | ## Show TagsEuler Tour, PURS |

### Module Progress:

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!