Euler Tour Trees

Trees are everywhere in computer science — file systems, parse trees, organisational charts, phylogenetic hierarchies. Algorithms on trees are generally easy when they work top-down: just recurse. But the moment someone asks "what is the sum of all values in this subtree?" or, worse, "now update that node's value — and answer the same query again", the naïve O(n) scan over the subtree stops being acceptable.

The Euler tour technique is a beautiful 1984 trick by Robert Tarjan and Uzi Vishkin that sidesteps the difficulty entirely. Walk the tree with a depth-first search and record, for every node, the moment you first visit it (its in-time) and the moment you leave it for the last time (its out-time). Write those times into an array as you go.

The magic: every subtree rooted at node $v$ occupies exactly the contiguous range $[\text{in}(v),\, \text{out}(v)]$ in that flat array. A subtree query becomes a range query on a sequence — and range queries are a solved problem, answerable in $O(\log n)$ with a segment tree or a Fenwick tree. Suddenly the entire toolkit of 1-D data structures is available for tree problems.

This article explores the technique, lets you build the tour interactively, and explains how it extends to fully dynamic trees where edges are inserted or deleted on the fly.

The tree below has seven nodes, each carrying a value. Press Run DFS to watch the depth-first search assign in-times and out-times. Then click any node and press Query subtree sum to see how its subtree becomes a contiguous range in the flat array.

<p class="hint">{{hint}}</p>
<div class="layout">
  <svg id="tree-svg" viewBox="0 0 340 220" width="340" height="220"></svg>
  <div class="panel">
    <div id="tour-display" class="tour-box">
      <div class="tour-label">{{tour_label}}</div>
      <div id="tour-cells" class="tour-cells"></div>
    </div>
    <div class="info-row">
      <span class="info-label">{{sel_node_label}}</span>
      <span id="sel-name">—</span>
    </div>
    <div class="info-row">
      <span class="info-label">{{in_out_label}}</span>
      <span id="sel-range">—</span>
    </div>
    <div class="info-row">
      <span class="info-label">{{subtree_sum_label}}</span>
      <span id="sel-sum">—</span>
    </div>
    <div class="status" id="status">{{status_initial}}</div>
    <div class="btns">
      <button id="btn-dfs" type="button">{{btn_run_dfs}}</button>
      <button id="btn-query" type="button" disabled>{{btn_query}}</button>
      <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
    </div>
  </div>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: 4px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.layout { display: flex; gap: 12px; align-items: flex-start; flex-wrap: wrap; }
svg { flex-shrink: 0; }
.panel { flex: 1; min-width: 180px; }
.tour-box { margin-bottom: .6rem; }
.tour-label { font-size: .78rem; color: #666; margin-bottom: 3px; }
.tour-cells { display: flex; gap: 3px; flex-wrap: wrap; }
.tc { width: 34px; height: 34px; display: flex; align-items: center; justify-content: center;
      font: 700 13px ui-monospace, monospace; border-radius: 5px;
      background: #e8eef3; border: 1px solid #cdd9e3; color: #1d3557; transition: background .2s; }
.tc.highlight { background: #fde68a; border-color: #f59e0b; }
.tc.active { background: #1d3557; color: #fff; border-color: #1d3557; }
.info-row { display: flex; gap: 6px; font-size: .85rem; margin-bottom: 3px; }
.info-label { color: #666; }
.status { font-size: .92rem; font-weight: 600; margin: .4rem 0; min-height: 1.3em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .4rem; flex-wrap: wrap; margin-top: .4rem; }
button { font: 600 13px system-ui; padding: .38rem .75rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button:disabled { opacity: .45; cursor: default; }
button.ghost { background: #fff; color: #1d3557; }
/* {{c_svg_styles}} */

// Code not found

Notice that the subtree of any node $v$ is always the slice $[\text{in}(v), \text{out}(v)]$ of the tour array. Checking the sum of a range is instant with a prefix-sum array; maintaining that prefix sum under updates uses a segment tree or Fenwick tree in $O(\log n)$ per operation. The same range trick also powers Lowest Common Ancestor queries — a topic closely related to dynamic shortest paths.

How fast is the Euler tour technique, and where does it stop working?

• Building the tour is a single DFS: $O(n)$ time, $O(n)$ space. Every node produces exactly one in-time and one out-time entry.
• Static subtree queries (sum, min, max, XOR …) reduce to range queries solvable in $O(\log n)$ with a segment tree or Fenwick tree, after $O(n)$ preprocessing.
• Point updates (change the value of one node) propagate to exactly one cell in the flat array: still $O(\log n)$ per update with a segment tree.
• The catch: structural changes. If an edge is inserted or deleted, in-times and out-times can shift for an entire subtree. Rebuilding naïvely costs $O(n)$.
• Dynamic trees (link-cut trees), introduced by Tarjan (1983), solve this by representing the Euler tour as a balanced BST (a splay tree) that can be split and joined in $O(\log n)$ amortized time. Every link (add edge) or cut (remove edge) is just a split-join pair — $O(\log n)$.
• ET-trees (Euler Tour Trees in the strict dynamic sense, by Henzinger and King, 1999) go further: they support the full suite of dynamic connectivity queries — "are nodes $u$ and $v$ in the same connected component?" — in $O(\log^2 n)$ per operation, a major result for online dynamic graph algorithms.

The bottom line: the flat-array encoding is $O(\log n)$ for everything that stays static, and the dynamic variants reach $O(\log n)$ or $O(\log^2 n)$ amortized even under arbitrary edge insertions and deletions — a proved and widely used result, not an open problem.

The Euler tour technique shows up wherever trees must answer queries quickly:

• Competitive programming: subtree sums, subtree max/min, and path queries are standard contest problems solved in $O(\log n)$ via the Euler tour plus a segment tree.
• Lowest Common Ancestor (LCA): the classical reduction records the Euler tour (visiting a node every time DFS enters or leaves a child) to turn LCA into a range-minimum query — solvable in $O(1)$ after $O(n \log n)$ preprocessing.
• Relational databases and XML engines: hierarchical data stored in the "nested sets" model encodes a tree exactly as an Euler tour, enabling SQL range predicates to answer "all descendants of node $v$" in a single index scan.
• Dynamic connectivity in networks: monitoring whether two routers are still in the same connected component after link failures uses ET-trees or link-cut trees under the hood.
• Compiler symbol tables: scoping rules ("is variable $x$ visible here?") map directly to the subtree membership test that an Euler tour makes trivial.

Master the Euler tour and you hold the key to the entire family of tree-to-sequence reductions — the same philosophy that makes dynamic shortest paths tractable in online settings.

The Euler tour is one of those tricks you learn once and reach for forever. A single depth-first walk stamps an in-time and out-time on every node, turning the branching chaos of a tree into a tidy flat sequence. From that moment, every subtree is just a contiguous range, and the entire archive of 1-D range-query algorithms — segment trees, Fenwick trees, sparse tables — becomes available.

When trees are dynamic, the tour itself is stored in a balanced BST that can be split and rejoined in $O(\log n)$, extending the same performance guarantee to link and cut operations. The result, proved by Henzinger and King in 1999, is a data structure that answers dynamic connectivity questions faster than any naïve approach and is widely deployed in practice.

The next time you face a tree problem that feels harder than a simple recursion, ask yourself: what does the Euler tour look like? More often than not, the answer reduces your tree to a sequence — and sequences are something computers are very, very good at.