The Euler Tour Technique: Turning Subtree Queries Into Range Queries

Tree problems with many queries like "sum of values in the subtree of v" or "add x to every node under v" become simple once you flatten the tree into an array. The Euler tour technique does exactly that.

Entry and exit times

Run a DFS and record when each node is first entered (tin) and when its subtree is finished (tout). Every node in v's subtree has an entry time in [tin[v], tout[v]], which is one contiguous range.

def flatten(adj, root=0):
    n = len(adj)
    tin, tout, order = [0] * n, [0] * n, []
    stack = [(root, -1, False)]
    while stack:
        v, p, done = stack.pop()
        if done:
            tout[v] = len(order) - 1
            continue
        tin[v] = len(order)
        order.append(v)
        stack.append((v, p, True))
        for u in adj[v]:
            if u != p:
                stack.append((u, v, False))
    return tin, tout, order

The iterative version avoids Python's recursion limit on deep trees, worth mentioning in an interview.

Subtree queries become range queries

• Place value[order[i]] at position i.
• Subtree sum of v = range sum over [tin[v], tout[v]]: use prefix sums if static, or a Fenwick or segment tree if values change.
• Add x to a whole subtree = range update on that interval (a Fenwick tree over a difference array).

Ancestor checks in O(1)

u is an ancestor of v exactly when tin[u] ≤ tin[v] and tout[v] ≤ tout[u]. That's a handy building block for LCA and path queries.

The other Euler tour

A second variant writes a node every time the DFS visits it, including on the way back up (length 2n − 1). Combined with a sparse table over depths, it gives O(1) LCA queries. Be clear which variant you mean.

Typical problems

• Count nodes in a subtree with a given colour (add offline sorting or Mo's on the flattened array).
• Company hierarchy: total salary under each manager, with raises applied to whole teams.
• Dynamic "is v in u's subtree?" checks.

Interview framing: "I'll flatten the tree with DFS entry and exit times so every subtree is a contiguous range, then use a Fenwick tree for updates and queries in O(log n)."

Disclosure: written by the team behind linkjob.ai, a real-time coding interview helper.