What Is an Euler Tour? From Königsberg Bridges to O(1) LCA

In 1736, Leonhard Euler asked whether you could walk across all seven bridges in Königsberg without crossing any bridge twice, then return to where you started. He proved you couldn't. Then he generalized the question, wrote a paper, and accidentally invented graph theory.

Not a bad afternoon.

That walk, when it does exist, is called an Euler tour (also called an Eulerian circuit or Eulerian cycle). The concept turns up in two places in coding interviews: directly in problems like LeetCode 332 (Reconstruct Itinerary), and indirectly as a tree technique that reduces lowest common ancestor queries to a range minimum problem. Both go by the same name, they have almost nothing in common, and yes, that is on purpose.

One Walk, Every Edge Once

An Euler tour is a closed walk through a graph that visits every edge exactly once and returns to its starting vertex. Every edge, used once. The graph doesn't care if you revisit vertices. It cares about edges.

A related concept is the Eulerian path: same constraint (each edge once), but you don't need to return to the start. The Eulerian path is strictly weaker. Every Eulerian circuit is also an Eulerian path, but not vice versa.

These two definitions get confused constantly. If an interview problem says "visit every edge exactly once," clarify whether the walk must be closed. It changes both the solvability check and the algorithm. Ask before you code anything.

Even Degrees or It Doesn't Work

An undirected graph has an Eulerian circuit if and only if every vertex has even degree and the graph is connected.

The intuition: every time the walk enters a vertex, it needs an unused edge to leave. If any vertex has odd degree, you'll eventually enter it with no way out. One odd-degree vertex is already a problem. Two odd-degree vertices give you an Eulerian path (start at one, end at the other), but not a circuit.

For directed graphs, the rule adjusts: each vertex's in-degree must equal its out-degree, and the graph must be strongly connected.

def has_euler_circuit(adj: dict[int, list[int]]) -> bool:
    return all(len(neighbors) % 2 == 0 for neighbors in adj.values())

The Königsberg graph has four vertices with degrees 3, 3, 3, and 5. Four odd-degree vertices. No Eulerian path, let alone a circuit. Euler didn't just solve the puzzle. He proved it was unsolvable, which is somehow more satisfying than a solution.

Hierholzer's Algorithm Runs in O(E)

Once you know the tour exists, you need to find it. Naive backtracking DFS works but can degrade badly. Hierholzer's algorithm finds an Eulerian circuit in O(E) time by following edges greedily and splicing sub-cycles together.

The insight: if you follow unused edges from any vertex until you get stuck, you've traced a cycle (because even degrees guarantee it). Now find any vertex in that cycle that still has unused edges, trace another cycle from there, and splice it in. Repeat until all edges are used. The implementation uses a stack and builds the result in reverse:

from collections import defaultdict

def euler_circuit(adj: dict[int, list[int]], start: int) -> list[int]:
    graph = defaultdict(list)
    for u, neighbors in adj.items():
        graph[u] = list(neighbors)

    stack = [start]
    circuit = []

    while stack:
        v = stack[-1]
        if graph[v]:
            u = graph[v].pop()
            stack.append(u)
        else:
            circuit.append(stack.pop())

    return circuit[::-1]

When graph[v] is empty, the current vertex has no way forward, so it's added to the circuit. The reversal at the end corrects the order. This runs in O(V + E) time and O(V + E) space.

LeetCode 332 (Reconstruct Itinerary) is Hierholzer's algorithm on a directed graph where you must also break ties lexicographically. The structure is the same. Just find an Eulerian path and respect direction.

The Tree Euler Tour: A Completely Different Thing

Here's where the naming gets interesting. Computer scientists looked at one technique, loved the name "Euler tour," and decided to use it again for something unrelated. A tree Euler tour is a DFS traversal that records every node visit, including re-visits when the DFS backtracks up the tree.

This has nothing to do with Hierholzer's algorithm. No edge traversal. No parity conditions. The name is the same because both involve traversing every element of a structure once, and apparently that was enough.

For a tree with N nodes, the tour has exactly 2N - 1 entries: each node appears once when first entered, and once more each time the DFS returns from one of its children.

def euler_tour(
    root: int, adj: dict[int, list[int]]
) -> tuple[list[int], dict[int, int]]:
    tour: list[int] = []
    first_occurrence: dict[int, int] = {}

    def dfs(node: int, parent: int) -> None:
        first_occurrence[node] = len(tour)
        tour.append(node)
        for child in adj[node]:
            if child != parent:
                dfs(child, node)
                tour.append(node)

    dfs(root, -1)
    return tour, first_occurrence

For a tree like this:

    1
   / \
  2   3
 / \
4   5

The tour is: [1, 2, 4, 2, 5, 2, 1, 3, 1]

Node 1 appears at positions 0, 6, and 8. Node 4 appears only at position 2. The structure encodes the shape of the tree as a flat sequence.

There are two Euler tours inside every competitive programming textbook. Computer scientists named them both the same thing.

LCA Becomes a Range Minimum Query

Here's the payoff. The lowest common ancestor of two nodes u and v is the shallowest node in the Euler tour between the first occurrences of u and v.

Why? The DFS visits every ancestor of v on the way down and revisits them on the way back up. Between the first visit to u and the first visit to v in the tour, every node encountered is either a descendant of their LCA or the LCA itself. The node with minimum depth in that window is the LCA.

def build_depth_array(tour: list[int], depth: dict[int, int]) -> list[int]:
    return [depth[node] for node in tour]

def lca_naive(
    u: int, v: int,
    tour: list[int],
    first: dict[int, int],
    depth: dict[int, int]
) -> int:
    left = min(first[u], first[v])
    right = max(first[u], first[v])
    min_depth = float("inf")
    result = -1
    for i in range(left, right + 1):
        if depth[tour[i]] < min_depth:
            min_depth = depth[tour[i]]
            result = tour[i]
    return result

This naive version is O(N) per query. The real power comes from pairing the Euler tour with a sparse table: preprocess the depth array in O(N log N), then answer any range minimum query in O(1). That gives you O(N log N) one-time preprocessing and O(1) per LCA query, the same result as more complex algorithms but with cleaner reasoning.

You can also use a segment tree instead, which gives O(N) preprocessing and O(log N) per query, or use the lowest common ancestor binary lifting approach if you only have a moderate number of queries.

Any Subtree Is Just a Range

The same DFS that builds the Euler tour also lets you collapse any subtree into a contiguous range. Record each node's entry time (when it's first added) and exit time (after all its descendants are processed). Every node in the subtree of u has an entry time in the range [entry[u], exit[u]].

def entry_exit(
    root: int, adj: dict[int, list[int]]
) -> tuple[dict[int, int], dict[int, int]]:
    entry: dict[int, int] = {}
    exit_: dict[int, int] = {}
    timer = [0]

    def dfs(node: int, parent: int) -> None:
        entry[node] = timer[0]
        timer[0] += 1
        for child in adj[node]:
            if child != parent:
                dfs(child, node)
        exit_[node] = timer[0] - 1

    dfs(root, -1)
    return entry, exit_

With entry and exit times, a subtree sum query becomes a range sum query on a flat array. Pair it with a Fenwick tree and you get O(log N) subtree updates and queries. This is the technique behind a class of problems that look unsolvable on trees until you realize the tree can be unrolled into an array by DFS order.

How the Costs Stack Up

Operation	Time	Space
Check Euler circuit existence	O(V + E)	O(1)
Hierholzer's algorithm	O(E)	O(V + E)
Build tree Euler tour	O(N)	O(N)
LCA with sparse table	O(N log N) build, O(1) query	O(N log N)
LCA with segment tree	O(N) build, O(log N) query	O(N)
Subtree queries (Fenwick)	O(N) build, O(log N) each	O(N)

The tour itself is always linear. The complexity of what you do with it depends on the range data structure you choose.

This Does Show Up in Interviews

Most of what's in this post comes from competitive programming, which is its own universe with its own rules. The Euler tour technique lived there for decades before it started appearing in hard interview problems at Google and similar companies.

Eulerian circuit problems appear more often than most engineers expect. LeetCode 332 (Reconstruct Itinerary) and 753 (Cracking the Safe) are both Hierholzer's in disguise. The existence check (are all degrees even, do directed in-degree and out-degree balance) comes up even when full construction isn't required.

The tree Euler tour is a harder ask. If you see a problem with O(Q) LCA queries on a static tree, this is the intended path. The DFS framework is the same one you already know. The Euler tour just asks you to record more information during that traversal.

Knowing the technique is one thing. Explaining it clearly under pressure, with someone watching, is another. If your instincts are solid but your live performance doesn't match, SpaceComplexity offers voice-based mock interviews with rubric-scored feedback on exactly this kind of structural reasoning.

Further Reading

• Seven Bridges of Königsberg, Wikipedia
• Eulerian path, Wikipedia
• Hierholzer's algorithm, Wikipedia
• LCA with Euler tour and RMQ, CP-Algorithms
• Sparse table for range minimum queries, CP-Algorithms