Introduction

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 vv occupies exactly the contiguous range [in(v),โ€‰out(v)][\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)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.

Try It: Build the Tour

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">A rooted tree with 7 nodes (values shown). Press <b>Run DFS</b> to assign in/out times,
    then click a node and press <b>Query subtree sum</b> to see the Euler-tour range in action.</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 array (in-order DFS):</div>
      <div id="tour-cells" class="tour-cells"></div>
    </div>
    <div class="info-row">
      <span class="info-label">Selected node:</span>
      <span id="sel-name">โ€”</span>
    </div>
    <div class="info-row">
      <span class="info-label">in-time / out-time:</span>
      <span id="sel-range">โ€”</span>
    </div>
    <div class="info-row">
      <span class="info-label">Subtree sum:</span>
      <span id="sel-sum">โ€”</span>
    </div>
    <div class="status" id="status">Press Run DFS to start.</div>
    <div class="btns">
      <button id="btn-dfs" type="button">Run DFS</button>
      <button id="btn-query" type="button" disabled>Query subtree sum</button>
      <button id="btn-reset" type="button" class="ghost">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; }
/* SVG node styles injected via JS */

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Euler Tour technique: DFS assigns in-time (entry) and out-time (exit) to each node.
// The subtree of node v is exactly the contiguous range [in(v), out(v)] in the tour array.
// Subtree sum = prefix[out(v)+1] - prefix[in(v)].  O(1) query after O(n) build.

// Tree definition: id, label, value, children
const NODES = {
  0: { label: 'A', val: 5, children: [1, 2] },
  1: { label: 'B', val: 3, children: [3, 4] },
  2: { label: 'C', val: 7, children: [5, 6] },
  3: { label: 'D', val: 2, children: [] },
  4: { label: 'E', val: 4, children: [] },
  5: { label: 'F', val: 1, children: [] },
  6: { label: 'G', val: 6, children: [] }
};
const ROOT = 0;

// Node positions in SVG (x, y)
const POS = {
  0: [170, 28],
  1: [85,  90],
  2: [255, 90],
  3: [40,  168],
  4: [130, 168],
  5: [210, 168],
  6: [300, 168]
};

// State
let inTime = {}, outTime = {}, tourArr = [], prefix = [];
let selected = null, dfsRan = false;

function dfs(id, timer) {
  inTime[id] = timer++;
  tourArr.push(id);
  for (const child of NODES[id].children) {
    timer = dfs(child, timer);
  }
  outTime[id] = timer - 1;
  return timer;
}

function buildTour() {
  inTime = {}; outTime = {}; tourArr = []; prefix = [];
  dfs(ROOT, 0);
  // Build prefix sums over values
  prefix[0] = 0;
  for (let i = 0; i < tourArr.length; i++) {
    prefix[i + 1] = prefix[i] + NODES[tourArr[i]].val;
  }
}

function subtreeSum(id) {
  // sum of values in subtree of id = prefix[out(id)+1] - prefix[in(id)]
  return prefix[outTime[id] + 1] - prefix[inTime[id]];
}

// โ”€โ”€ SVG rendering โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
const NS = 'http://www.w3.org/2000/svg';
const svg = document.getElementById('tree-svg');

function makeSVGEl(tag, attrs) {
  const el = document.createElementNS(NS, tag);
  for (const [k, v] of Object.entries(attrs)) el.setAttribute(k, v);
  return el;
}

function renderSVG() {
  svg.innerHTML = '';
  // Draw edges first
  for (const [id, node] of Object.entries(NODES)) {
    for (const child of node.children) {
      const [x1, y1] = POS[id];
      const [x2, y2] = POS[child];
      svg.appendChild(makeSVGEl('line', { x1, y1, x2, y2, stroke: '#94a3b8', 'stroke-width': 1.8 }));
    }
  }
  // Draw nodes
  for (const [id, node] of Object.entries(NODES)) {
    const [cx, cy] = POS[id];
    const nid = Number(id);
    const isSelected = nid === selected;
    const hasTime = dfsRan && inTime[nid] !== undefined;

    const fill = isSelected ? '#1d3557' : (hasTime ? '#e8eef3' : '#c9ccd1');
    const stroke = isSelected ? '#1d3557' : '#94a3b8';
    const textFill = isSelected ? '#fff' : '#1d3557';

    const g = makeSVGEl('g', { style: 'cursor:pointer' });
    g.addEventListener('click', () => selectNode(nid));
    g.appendChild(makeSVGEl('circle', { cx, cy, r: 22, fill, stroke, 'stroke-width': 1.8 }));

    // Label (A, B, Cโ€ฆ)
    const lbl = makeSVGEl('text', { x: cx, y: cy - 4, 'text-anchor': 'middle',
      'font-size': 13, 'font-weight': 700, fill: textFill, 'font-family': 'system-ui' });
    lbl.textContent = node.label + '=' + node.val;
    g.appendChild(lbl);

    // In/out times below label
    if (hasTime) {
      const t = makeSVGEl('text', { x: cx, y: cy + 11, 'text-anchor': 'middle',
        'font-size': 9.5, fill: isSelected ? '#cdd9e3' : '#64748b', 'font-family': 'ui-monospace, monospace' });
      t.textContent = inTime[nid] + 'โ€“' + outTime[nid];
      g.appendChild(t);
    }
    svg.appendChild(g);
  }
}

// โ”€โ”€ Tour cells โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
function renderTour() {
  const container = document.getElementById('tour-cells');
  container.innerHTML = '';
  if (!dfsRan) { container.textContent = 'โ€”'; return; }
  const lo = selected !== null ? inTime[selected] : -1;
  const hi = selected !== null ? outTime[selected] : -2;
  tourArr.forEach((id, i) => {
    const d = document.createElement('div');
    d.className = 'tc' + (i >= lo && i <= hi ? ' highlight' : '') + (i === lo ? ' active' : '');
    d.title = fmt('pos %i%: %label%(%val%)', { i: i, label: NODES[id].label, val: NODES[id].val });
    d.textContent = NODES[id].label;
    container.appendChild(d);
  });
}

// โ”€โ”€ Interaction โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
function selectNode(id) {
  if (!dfsRan) {
    setStatus('Run DFS first to assign times.', 'bad');
    return;
  }
  selected = id;
  document.getElementById('sel-name').textContent = fmt('%label% (value=%val%)', { label: NODES[id].label, val: NODES[id].val });
  document.getElementById('sel-range').textContent = inTime[id] + ' / ' + outTime[id];
  document.getElementById('sel-sum').textContent = 'โ€”';
  document.getElementById('btn-query').disabled = false;
  setStatus('Click "Query subtree sum" to compute.', '');
  renderSVG();
  renderTour();
}

function setStatus(msg, cls) {
  const el = document.getElementById('status');
  el.textContent = msg;
  el.className = 'status ' + cls;
}

document.getElementById('btn-dfs').addEventListener('click', () => {
  buildTour();
  dfsRan = true;
  selected = null;
  document.getElementById('sel-name').textContent = 'โ€”';
  document.getElementById('sel-range').textContent = 'โ€”';
  document.getElementById('sel-sum').textContent = 'โ€”';
  document.getElementById('btn-query').disabled = true;
  setStatus('DFS complete! Click a node to select it.', 'ok');
  renderSVG();
  renderTour();
  // Log verification data
  console.log('Tour:', tourArr.map(i => NODES[i].label).join(' โ†’ '));
  console.log('in-times:', Object.fromEntries(Object.entries(inTime).map(([k,v])=>[NODES[k].label,v])));
  console.log('out-times:', Object.fromEntries(Object.entries(outTime).map(([k,v])=>[NODES[k].label,v])));
  console.log('prefix sums:', prefix);
});

document.getElementById('btn-query').addEventListener('click', () => {
  if (selected === null) return;
  const sum = subtreeSum(selected);
  document.getElementById('sel-sum').textContent = sum;
  setStatus(
    fmt('Subtree of %label%: range [%v%, %v2%] โ†’ sum = %sum%', { label: NODES[selected].label, v: inTime[selected], v2: outTime[selected], sum: sum }), 'ok'
  );
  renderTour();
  // Verify: naive sum
  function naiveSum(id) {
    let s = NODES[id].val;
    for (const c of NODES[id].children) s += naiveSum(c);
    return s;
  }
  const naive = naiveSum(selected);
  console.assert(sum === naive,
    fmt('FAIL: euler sum=%sum% vs naive=%naive% for node %label%', { sum: sum, naive: naive, label: NODES[selected].label }));
  console.log(fmt('Euler sum for %label%=%sum% (naive=%naive%) โœ“', { label: NODES[selected].label, sum: sum, naive: naive }));
});

document.getElementById('btn-reset').addEventListener('click', () => {
  dfsRan = false; selected = null;
  inTime = {}; outTime = {}; tourArr = []; prefix = [];
  document.getElementById('sel-name').textContent = 'โ€”';
  document.getElementById('sel-range').textContent = 'โ€”';
  document.getElementById('sel-sum').textContent = 'โ€”';
  document.getElementById('btn-query').disabled = true;
  setStatus('Press Run DFS to start.', '');
  renderSVG();
  renderTour();
});

// Initial render
renderSVG();
renderTour();
Result
Console

Notice that the subtree of any node vv is always the slice [in(v),out(v)][\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)O(\log n) per operation. The same range trick also powers Lowest Common Ancestor queries โ€” a topic closely related to dynamic shortest paths.

The Real Complexity

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

  • Building the tour is a single DFS: O(n)O(n) time, O(n)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)O(\log n) with a segment tree or Fenwick tree, after O(n)O(n) preprocessing.
  • Point updates (change the value of one node) propagate to exactly one cell in the flat array: still O(logโกn)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)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)O(\log n) amortized time. Every link (add edge) or cut (remove edge) is just a split-join pair โ€” O(logโกn)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 uu and vv in the same connected component?" โ€” in O(logโก2n)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)O(\log n) for everything that stays static, and the dynamic variants reach O(logโกn)O(\log n) or O(logโก2n)O(\log^2 n) amortized even under arbitrary edge insertions and deletions โ€” a proved and widely used result, not an open problem.

Where It Matters

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)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)O(1) after O(nlogโกn)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 vv" 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 xx 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.

Conclusion

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)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.

Share this article

Pick a channel โ€” or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/euler-tour-trees/Content licensed under CC BY-NC 4.0.