Reconstruct Itinerary: Hierholzer's Algorithm for Eulerian Paths
Solve Reconstruct Itinerary with Hierholzer's algorithm — a greedy post-order DFS that walks every ticket once and rebuilds the Eulerian path in JavaScript.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
You have a stack of plane tickets, each one a [from, to] pair, and you dropped them on the floor. Your job is to put them back in order so they form a single trip that starts at JFK and uses every ticket exactly once. When more than one valid trip exists, you want the one that reads smallest alphabetically.
The naive move is to treat this like a maze and backtrack through every branch. That works, but it re-explores dead ends over and over. The clean solution walks the graph once, never undoing a step, and still lands on the correct order — as long as you record airports at the right moment. That trick has a name: Hierholzer's algorithm for finding an Eulerian path.
The problem
You are given a list of tickets where tickets[i] = [from, to]. Reconstruct the itinerary as a single ordered list of airports. Every ticket must be used exactly once, the trip must begin at JFK, and if several valid itineraries exist, return the one that is lexicographically smallest when read as a single string of airport codes.
The problem guarantees the tickets do form at least one valid itinerary, so you never have to report failure — you only have to find the smallest one.
Input: [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
Output: ["JFK","MUC","LHR","SFO","SJC"]Two constraints do all the heavy lifting. "Use every ticket exactly once" is the definition of an Eulerian path — a walk that crosses every edge of a graph once. "Lexicographically smallest" means that whenever you stand at an airport with several outbound tickets, you should prefer the alphabetically earliest destination first.
The brute force baseline
Model each airport as a node and each ticket as a directed edge. Then run a depth-first search that tries to consume all tickets, backtracking whenever it hits a dead end before every ticket is used.
function findItinerary(tickets) {
const graph = {};
for (const [from, to] of tickets) {
(graph[from] ||= []).push(to);
}
for (const node in graph) graph[node].sort();
const total = tickets.length;
const route = ["JFK"];
function backtrack(airport) {
if (route.length === total + 1) return true;
const dests = graph[airport] || [];
for (let i = 0; i < dests.length; i++) {
const next = dests[i];
dests.splice(i, 1); // use this ticket
route.push(next);
if (backtrack(next)) return true;
route.pop(); // undo
dests.splice(i, 0, next); // put the ticket back
}
return false;
}
backtrack("JFK");
return route;
}Because destinations are sorted, the first complete itinerary this finds is automatically the lexicographically smallest. But look at the cost: every dead end forces a full unwind — pop the airport, splice the ticket back, try the next branch. With many crossing routes the number of partial paths explodes, and the worst case is exponential. On a dense set of tickets this times out.
The key insight
Hierholzer's algorithm removes the backtracking entirely. The reframe is this: you never have to undo a wrong turn if you record airports in post-order.
Walk greedily — always take the alphabetically smallest unused ticket out of your current airport, and delete that ticket as you take it. Keep going until you land somewhere with no tickets left. That airport is a dead end, and here is the key move: append it to a result buffer only when you get stuck, then step back to the previous airport and keep draining its remaining tickets.
Why does this work? In an Eulerian path, exactly one airport (the true final destination) runs out of edges while everything else is still reachable. When your greedy walk gets stuck early — like flying JFK → KUL when KUL has no outbound ticket — that dead-end airport is genuinely the last stop of its branch, so it belongs at the end of the itinerary. Recording it first and reversing at the end puts it exactly where it belongs. The main circuit naturally wraps around any dead-end spur because those spurs get flushed to the buffer before the circuit's own airports do.
The optimal solution
This is the algorithm the visualizer animates, line for line: build a sorted adjacency list, run a DFS that shifts destinations off the front, push each airport in post-order, and reverse the buffer at the end.
var findItinerary = function(tickets) {
let graph = {};
for (let [from, to] of tickets) {
if (!graph[from]) graph[from] = [];
graph[from].push(to);
}
for (let node in graph) {
graph[node].sort();
}
let path = [];
let dfs = (curr) => {
while (graph[curr] && graph[curr].length) {
let neighbor = graph[curr].shift();
dfs(neighbor);
}
path.push(curr);
};
dfs("JFK");
return path.reverse();
};Three details carry the whole solution. Sorting each airport's list once means shift() always hands back the lexicographically smallest remaining ticket — no per-step search. Calling shift() consumes the ticket, so the while loop naturally terminates when an airport is drained. And path.push(curr) runs only after the loop finishes draining — that is the post-order recording that makes dead ends land at the front of the buffer, ready to be flipped into place by path.reverse().
Walkthrough
Trace tickets = [["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]]. After building and sorting, the graph is JFK: [KUL, NRT], NRT: [JFK]. Greedy order sends us to KUL first — a dead end — which is exactly the case that breaks naive greedy but Hierholzer handles cleanly.
| Step | Action | Call stack | Result buffer |
|---|---|---|---|
| 1 | dfs(JFK) — shift KUL from [KUL, NRT] | JFK | [] |
| 2 | dfs(KUL) — no tickets, drop out of loop | JFK, KUL | [] |
| 3 | push KUL (dead end), return to JFK | JFK | [KUL] |
| 4 | back in JFK — shift NRT from [NRT] | JFK | [KUL] |
| 5 | dfs(NRT) — shift JFK from [JFK] | JFK, NRT | [KUL] |
| 6 | dfs(JFK) — no tickets left, drop out | JFK, NRT, JFK | [KUL] |
| 7 | push JFK, return to NRT | JFK, NRT | [KUL, JFK] |
| 8 | NRT drained — push NRT, return to JFK | JFK | [KUL, JFK, NRT] |
| 9 | JFK drained — push JFK | (empty) | [KUL, JFK, NRT, JFK] |
| 10 | path.reverse() | — | [JFK, NRT, JFK, KUL] |
The final itinerary is JFK → NRT → JFK → KUL. Notice that KUL, the airport we greedily flew to first, ends up last — because it was the earliest dead end, it was the first thing pushed, so reversing sinks it to the bottom. A naive greedy that committed to JFK → KUL and quit would have been stuck; post-order recording rescues it automatically.
Complexity
Let E be the number of tickets (edges) and V the number of airports (nodes).
| Metric | Big-O | Why |
|---|---|---|
| Time | O(E log E) | Sorting every airport's destination list dominates; the DFS itself visits each of the E edges exactly once |
| Space | O(E) | The adjacency list stores all E tickets, the result buffer holds E + 1 airports, and the recursion stack can reach depth E |
The traversal alone is O(E) because each shift() permanently removes a ticket, so no edge is ever revisited. The log E factor comes purely from sorting destinations up front to guarantee lexicographic order.
Common mistakes
- Recording airports in pre-order. Pushing
currbefore the loop drains its tickets breaks the dead-end handling entirely. The post-order push is the whole algorithm — move it and you get a scrambled path. - Forgetting to reverse. The buffer is built deepest-first, so it comes out backwards. Skip
path.reverse()and you return the itinerary in reverse order. - Not sorting destinations. Without the sort,
shift()hands back tickets in insertion order, and you lose the lexicographically-smallest guarantee. You would still get a valid itinerary, just not the required one. - Falling back to greedy without post-order. Committing to the first smallest ticket and never revisiting fails the moment that choice leads to a dead end before all tickets are used — the
JFK → KULtrap above. - Sorting once globally instead of per airport. Each airport needs its own sorted list; a single flat sort of all tickets does not give you per-node ordering.
Where this pattern shows up next
Reconstruct Itinerary is a graph-traversal problem in disguise, and the surrounding graph toolkit is worth knowing cold:
- Redundant Connection — detect the one edge that turns a tree into a graph with a cycle, using union-find.
- Course Schedule II — order nodes so every prerequisite comes first, the topological-sort cousin of ordering flights.
- Shortest Path in Binary Matrix — BFS layer-by-layer for the fewest-steps path through a grid.
- Network Delay Time — Dijkstra on a weighted graph to find how long a signal takes to reach every node.
You can also open the Reconstruct Itinerary visualizer to watch the adjacency lists drain, the recursion stack grow, and the post-order buffer fill one airport at a time.
FAQ
What is Hierholzer's algorithm?
Hierholzer's algorithm finds an Eulerian path or circuit — a walk that uses every edge of a graph exactly once. It works by following unused edges greedily until it gets stuck, recording each node in post-order as it backtracks, and reversing the recorded sequence at the end. For Reconstruct Itinerary, the edges are tickets and the "stuck" moments correspond to dead-end airports that belong at the tail of the trip.
Why does the post-order DFS produce the correct itinerary?
Because the airport where your greedy walk runs out of tickets is genuinely the last stop of that branch. Recording it first, then continuing to drain the airports above it on the recursion stack, builds the itinerary from the end backwards. Reversing the buffer flips it into forward order. Any dead-end spur gets flushed to the buffer before the main circuit, so the circuit correctly wraps around it — no backtracking or undo required.
How do we guarantee the lexicographically smallest itinerary?
By sorting each airport's list of destinations once, up front. Since the DFS always shift()s from the front of the list, it consumes the alphabetically smallest available ticket at every airport. That greedy-smallest choice, combined with Hierholzer's post-order recording, yields the smallest valid ordering overall — you never have to compare whole itineraries against each other.
What is the time complexity of Reconstruct Itinerary?
O(E log E), where E is the number of tickets. The DFS visits each ticket exactly once for O(E) traversal, because shift() permanently removes a ticket so no edge is revisited. The dominant cost is sorting every airport's destination list to enforce lexicographic order, which totals O(E log E). Space is O(E) for the adjacency list, result buffer, and recursion stack.
Why not just use greedy DFS without recording in post-order?
Plain greedy fails when the smallest-first choice leads to a dead end before all tickets are used. Take [["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]]: greedy flies JFK → KUL, but KUL has no outbound ticket while two tickets remain, so the walk is stuck. Post-order recording sidesteps this — it lets the dead-end KUL be pushed to the buffer and sink to the end after reversal, while the real circuit JFK → NRT → JFK is recorded around it.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.