Eulerian Paths and Reconstruct Itinerary

Every graph problem so far has been about visiting nodes. This one is about visiting edges — walk every edge exactly once, and you have an Eulerian path. It is the problem Euler solved in 1736 with the bridges of Königsberg, which makes it the oldest result in graph theory, and it still appears in interviews as LeetCode 332.

It matters here for one reason: a normal DFS gets it wrong. The natural recursive traversal produces a plausible answer that is not a valid itinerary, and understanding why is the entire lesson.

What you’ll learn

• The degree conditions that decide whether an Eulerian path or circuit exists at all — usually answerable in one pass, before writing any traversal.
• Hierholzer’s algorithm, and why it appends nodes after the recursion rather than before.
• Why an ordinary DFS fails on LeetCode 332, and what “getting stuck” means.
• How the lexicographic requirement is satisfied for free by a heap.

The cue

You are looking at an Eulerian path when…

• The problem asks you to use every edge exactly once — every ticket, every road, every domino, every pair of letters.
• Nodes may be revisited freely. That is the tell that distinguishes this from a Hamiltonian path (every node once, which is NP-hard) — Eulerian is polynomial, and conflating the two is an expensive mistake.
• The answer is an ordering of edges, often required to be lexicographically smallest.

Check feasibility before coding. For a directed graph an Eulerian path exists iff the graph is connected when viewed as undirected, and either every node has in == out, or exactly one node has out = in + 1 (the start) and exactly one has in = out + 1 (the end). For an undirected graph: connected, and either zero or exactly two nodes have odd degree. Stating that condition is often most of the credit.

Reach for something else when every node must be visited once (Hamiltonian — NP-hard, so think backtracking or bitmask DP), or when you need a shortest walk rather than a complete one.

Visual intuition

The underlying traversal is still a DFS — what changes is when a node is recorded and that edges, not nodes, are consumed:

graphA DFS over edges rather than nodesthe traversal Hierholzer builds on

stack

JFK

1def dfs(graph, start):2    seen, order = set(), []3    stack = [start]4    while stack:5        node = stack.pop()          # LIFO — the only line that differs from BFS6        if node in seen: continue7        seen.add(node)8        order.append(node)9        for nxt in reversed(graph[node]):10            if nxt not in seen:11                stack.append(nxt)12    return order

seedPush JFK. The *only* structural difference from BFS is that this container pops from the end instead of the front — swap the deque for a list and breadth becomes depth.

Play‹›1/5⟲

Watch the stack. Hierholzer's insight is that a node should be appended to the answer only when it has no unused edges left — that is, on the way OUT of the recursion, not on the way in. Appending on entry gives the order shown here, which is not a valid itinerary.

Why a normal DFS fails

Take tickets = [[JFK,SFO], [JFK,ATL], [SFO,ATL], [ATL,JFK], [ATL,SFO]] and ask for the lexicographically smallest itinerary from JFK.

A greedy DFS takes the alphabetically smallest option at every step:

step	at	takes	remaining edges from here
1	JFK	ATL (before SFO)	SFO
2	ATL	JFK	SFO
3	JFK	SFO	—
4	SFO	ATL	—
5	ATL	SFO	—
6	SFO	stuck	—

It ends at SFO having used all five edges, which happens to work here. Now reorder slightly and the greedy walks into a dead end with edges still unused — and a plain DFS has no way to recover, because it has already committed to the order it printed.

This is the whole point of Hierholzer’s algorithm

Getting stuck is not a bug to avoid — it is guaranteed to happen, and it happens exactly at the end of the itinerary. So instead of fighting it, use it: append a node to the answer only when it has no unused edges left, then reverse at the end. A node that gets stuck is appended first and therefore ends up last, which is precisely where it belongs.

That inversion — record on the way out, then reverse — is the algorithm.

The template

hierholzer.py

from collections import defaultdict
import heapq
 
 
def find_itinerary(tickets):
    # Min-heap per node gives lexicographic order for free.
    graph = defaultdict(list)
    for src, dst in tickets:
        heapq.heappush(graph[src], dst)
 
    route = []
 
    def visit(node):
        # Consume edges until this node is exhausted...
        while graph[node]:
            nxt = heapq.heappop(graph[node])   # removing IS marking used
            visit(nxt)
        # ...then record it. Post-order is the entire trick.
        route.append(node)
 
    visit("JFK")
    return route[::-1]                          # reverse: stuck node ends last
 
 
def find_itinerary_iterative(tickets):
    graph = defaultdict(list)
    for src, dst in tickets:
        heapq.heappush(graph[src], dst)
 
    stack, route = ["JFK"], []
    while stack:
        while graph[stack[-1]]:
            stack.append(heapq.heappop(graph[stack[-1]]))
        route.append(stack.pop())               # exhausted — record it
    return route[::-1]
 
 
tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
print(find_itinerary(tickets))
# expect ['JFK', 'MUC', 'LHR', 'SFO', 'SJC']
print(find_itinerary_iterative(tickets))

Note there is no visited set. Edges are marked used by being popped out of the adjacency structure, which is the right model — this is about consuming edges, not marking nodes, and nodes are revisited on purpose.

Dry run

tickets = [[JFK,SFO], [JFK,ATL], [SFO,ATL], [ATL,JFK], [ATL,SFO]], starting at JFK. Heaps: JFK: [ATL, SFO], ATL: [JFK, SFO], SFO: [ATL].

depth	at	pops	route (append order)
1	JFK	ATL	—
2	ATL	JFK	—
3	JFK	SFO	—
4	SFO	ATL	—
5	ATL	SFO	—
6	SFO	exhausted	[SFO]
5	ATL	exhausted	[SFO, ATL]
4	SFO	exhausted	[SFO, ATL, SFO]
3	JFK	exhausted	[SFO, ATL, SFO, JFK]
2	ATL	exhausted	[…, ATL]
1	JFK	exhausted	[SFO, ATL, SFO, JFK, ATL, JFK]

Reversed: JFK → ATL → JFK → SFO → ATL → SFO — all five edges, each once, lexicographically smallest.

Read the append column again. SFO was recorded first because it got stuck first, and reversing puts it last where it belongs. Every node appears in the answer as many times as it is passed through, which is why nodes are not marked visited.

Complexity

Aspect	Cost
Feasibility check (degrees + connectivity)	$O(V + E)$
Hierholzer with plain lists	$O(V + E)$
Hierholzer with a heap per node (lexicographic)	$O(E \log E)$
Space	$O(V + E)$ for the graph, $O(E)$ for the route

The $\log$ factor is the price of the lexicographic requirement, not of the algorithm. Pre-sorting each adjacency list and popping from the end is the same cost overall and slightly faster in practice — worth mentioning.

The variant map

Variant	Condition	Canonical problem
Eulerian path, directed	connected; in == out everywhere, or one node out = in + 1 and one in = out + 1	332 Reconstruct Itinerary
Eulerian circuit, directed	connected; in == out for every node	2097 Valid Arrangement of Pairs
Eulerian path, undirected	connected; 0 or 2 nodes of odd degree	classic Königsberg
De Bruijn sequence	Eulerian circuit on a de Bruijn graph	753 Cracking the Safe
Domino / word chains	model each tile as an edge, not a node	interview favourite

LC 753 Cracking the Safe is an Eulerian circuit in disguise

Nodes are length-(n-1) strings, and each of the k possible next digits is an edge. Every node has in-degree and out-degree exactly k, so an Eulerian circuit always exists, and walking it produces a sequence containing every length-n combination exactly once. Recognising the modelling is the whole problem; the traversal is this page’s template unchanged.

Pitfalls

• Appending the node before the recursion. Pre-order gives an invalid itinerary. It must be post-order, then reversed — this is the single defining detail.
• Using a visited set on nodes. Nodes are revisited deliberately. Only edges are consumed, by removing them.
• Forgetting to reverse. The route is built backwards. The un-reversed output is a valid path through the reverse graph, which makes it look almost right.
• Confusing Eulerian with Hamiltonian. Every edge once is polynomial; every node once is NP-hard. Reaching for backtracking here is a large, avoidable cost.
• Skipping the feasibility check. A graph with two nodes of out = in + 1 has no Eulerian path at all, and the traversal will happily return a partial answer rather than saying so.
• Assuming connectivity. Isolated edges make the path impossible even when every degree is balanced.

Interview follow-ups

They ask	What they’re checking	The answer
“How do you know an Eulerian path exists?”	Whether you check before coding	Directed: connected, and either all in == out or exactly one node with out = in + 1 and one with in = out + 1. Undirected: connected, and 0 or 2 odd-degree nodes
“Why post-order and not pre-order?”	The defining insight	Getting stuck is guaranteed and happens at the end of the itinerary. Recording on exit and reversing puts the stuck node last, where it belongs
“Why no visited set?”	Whether you understand the model	Edges are consumed, nodes are not. A valid itinerary revisits airports repeatedly
“How is lexicographic order guaranteed?”	Data-structure choice	A min-heap per node, or pre-sort each adjacency list. It costs the $\log$ factor and nothing else
“Eulerian or Hamiltonian?”	Whether you know the boundary	Eulerian visits every edge and is $O(V + E)$. Hamiltonian visits every node and is NP-hard — completely different tools
“Recursion depth on 10,000 tickets”	Practical limits	Depth equals edge count, so Python’s default limit is exceeded. Use the iterative stack version — which is why it is given above

Practice

1 problems

0 easy0 medium1 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

• ○332Reconstruct ItineraryhardNeetCode 150

Exercises

LC 332 — Reconstruct Itinerary · Hard

pch.exerciseTag pch.exerciseTitle

Feasibility check — directed Eulerian path

pch.exerciseTag pch.exerciseTitle

Iterative Hierholzer — avoiding the recursion limit

pch.exerciseTag pch.exerciseTitle

Self-check

pch.quizTag Eulerian paths — self-check

1. What distinguishes an Eulerian path from a Hamiltonian path, and why does it matter enormously?

   A Eulerian is for directed graphs, Hamiltonian for undirected B Eulerian visits every EDGE once and is O(V+E); Hamiltonian visits every NODE once and is NP-hard C They are the same thing D Hamiltonian allows revisiting nodes
   pch.quizShowAnswer

   B — Eulerian visits every EDGE once and is O(V+E); Hamiltonian visits every NODE once and is NP-hard — Conflating them is expensive: you either reach for backtracking on a polynomial problem, or hunt for a polynomial algorithm that does not exist. 'Nodes may be revisited' is the tell for Eulerian.

2. Why is the node appended AFTER the recursion rather than before?

   A For efficiency B Because getting stuck is guaranteed and happens at the END of the itinerary — recording on exit and reversing puts the stuck node last, where it belongs C To avoid infinite loops D Pre-order also works
   pch.quizShowAnswer

   B — Because getting stuck is guaranteed and happens at the END of the itinerary — recording on exit and reversing puts the stuck node last, where it belongs — This is the whole algorithm. A plain pre-order DFS commits to an order it cannot revise, so it produces a plausible but invalid itinerary when it dead-ends with edges unused.

3. Why is there no visited set?

   A It is an oversight in the standard solution B Because edges are consumed by being removed from the adjacency structure — nodes are revisited on purpose, since a valid itinerary passes through airports repeatedly C Because the graph is a tree D A visited set is required
   pch.quizShowAnswer

   B — Because edges are consumed by being removed from the adjacency structure — nodes are revisited on purpose, since a valid itinerary passes through airports repeatedly — The model is edge consumption, not node marking. Adding a visited set on nodes would forbid exactly the revisits the answer requires.

4. For a directed graph, when does an Eulerian PATH (not circuit) exist?

   A Whenever the graph is connected B Connected, and either every node has in == out, or exactly one node has out = in + 1 and exactly one has in = out + 1 C When every node has even degree D When there are no cycles
   pch.quizShowAnswer

   B — Connected, and either every node has in == out, or exactly one node has out = in + 1 and exactly one has in = out + 1 — The two unbalanced nodes are the start and the end. Checking this in one O(V+E) pass before writing any traversal is often most of the credit on this problem.

5. How is the lexicographically smallest itinerary guaranteed?

   A By sorting the final route B By a min-heap per node (or pre-sorting each adjacency list), so the smallest unused destination is always taken first C By trying all orderings D It is not guaranteed
   pch.quizShowAnswer

   B — By a min-heap per node (or pre-sorting each adjacency list), so the smallest unused destination is always taken first — Sorting the final route would destroy it — the route is a path, not a set. The ordering must be enforced at each choice point, and that costs only the log factor.

Recall card

• Cue — use every edge exactly once; nodes may repeat. Answer is an ordering of edges, often lexicographically smallest.
• Feasibility first — directed: connected, and all in == out, or one node out = in + 1 and one in = out + 1. Undirected: connected, and 0 or 2 odd-degree nodes.
• Hierholzer — consume edges from a node until exhausted, then append the node; reverse at the end.
• No visited set — popping the edge is what marks it used.
• Complexity — $O(V + E)$, or $O(E \log E)$ with a heap for lexicographic order.
• Not Hamiltonian — every node once is NP-hard. Check which you have.

Recap

• Eulerian paths are about edges, not nodes, and that single distinction separates a polynomial problem from an NP-hard one.
• The degree conditions answer “is it even possible” in one pass, before any traversal.
• Hierholzer’s algorithm works with getting stuck rather than against it: append on the way out, then reverse.
• LeetCode 332 is the canonical form, and 753 Cracking the Safe is the same algorithm behind a modelling problem.

Next: Union-Find Problem Patterns — the other way to reason about connectivity, and when it beats a traversal.