Eulerian path (Hierholzer)
Walk greedily, back out when stuck, and record nodes post-order; reverse at the end.
A node is appended only when all its edges are used.
01The intuition
Start with what you would do by hand
You have a pile of plane tickets, each from one airport to another: JFK → SFO, JFK → ATL, SFO → ATL, ATL → JFK, ATL → SFO. You must use every ticket exactly once, starting at JFK, and if several orders work, choose the one that is alphabetically first. By hand you start flying: JFK, cheapest alphabetically is ATL, then from ATL to JFK, then SFO, then ATL, then SFO. Every ticket used. The trip is JFK, ATL, JFK, SFO, ATL, SFO.
That worked because greed happened to never strand us. It can fail: from JFK, flying to the alphabetically earlier airport could lead to a dead end while unused tickets remain elsewhere. Then you would have to back up and try another order, and with hundreds of tickets the retrying explodes.
Build the structure, one piece at a time
Piece one: for each airport, the list of destinations, sorted alphabetically: JFK: [ATL, SFO], ATL: [JFK, SFO], SFO: [ATL]. We will consume tickets from the front of each list.
Piece two: a stack holding the airports of the trip so far, like a stack of visited places. Push JFK.
Piece three, the rule (Hierholzer): look at the airport on top of the stack. If it still has a ticket, take the first one, push the destination. If it has none, it is a dead end; pop it and write it to the end of the answer. Keep going until the stack is empty, then reverse the answer.
- Stack [JFK]. JFK has ATL: push. [JFK, ATL].
- ATL has JFK: push. [JFK, ATL, JFK]. JFK has SFO: push. [..., SFO]. SFO has ATL: push. ATL has SFO: push. Stack [JFK, ATL, JFK, SFO, ATL, SFO].
- SFO has nothing: pop, answer = [SFO]. ATL has nothing: pop, answer = [SFO, ATL]. SFO: pop. JFK: pop. ATL: pop. JFK: pop. Answer = [SFO, ATL, SFO, JFK, ATL, JFK].
- Reverse: JFK, ATL, JFK, SFO, ATL, SFO.
The clever part is what happens when greed strands you early: the dead end gets written first, which after reversing puts it last, and the stack naturally backs up to an airport with tickets left and continues from there.
Why it is correct
The invariant: an airport is written to the answer only when it has no unused ticket. So read backwards, the answer begins at the start, and each airport written just before another was reached by a ticket from it; the detours the stack unwinds are closed loops that get spliced in. The standard theorem says an Eulerian path exists exactly when every airport has as many arrivals as departures, except possibly the start (one extra departure) and the end (one extra arrival), and the problem promises this. Taking destinations in sorted order makes the first complete trip found the alphabetically smallest, because any earlier choice would have been tried first and only abandoned if it could not use all tickets.
Why it is fast
Each ticket is consumed once, each airport is pushed once per arrival and popped once. Sorting each destination list costs the log factor:
work ≈ E log E, against the factorial number of orders a retry search could try
How to recognise it in an interview
Cues: "use every ticket, edge or pair exactly once", "reconstruct the itinerary", "a sequence where consecutive items chain", "shortest string containing every code". The first thing to say: "this is an Eulerian path; walk greedily, record on dead ends, reverse." Reconstruct Itinerary is the example above. Cracking the Safe builds a graph whose nodes are the last n − 1 digits and whose edges are digits, then the same walk gives the shortest superstring.
02The idea in one line
Walk greedily, back out when stuck, and record nodes post-order; reverse at the end.
Reach for it when: Reconstruct itinerary, valid arrangement of pairs, cracking the safe.
Cost: O(E log E) time.
03The walk-through, step by step
The video works one example: Reconstruct Itinerary JFK→SFO→ATL→JFK→ATL→SFO. These are its captions in order, so you can follow without the video or check a step you missed.
- Sort each airport's tickets; walk greedily, back out when stuck
- Start at JFK
- JFK still has a ticket: fly to ATL
- ATL still has a ticket: fly to JFK
- JFK still has a ticket: fly to SFO
- SFO still has a ticket: fly to ATL
- ATL still has a ticket: fly to SFO
- SFO has no tickets left: stuck, write it at the end
- ATL has no tickets left: stuck, write it at the end
- SFO has no tickets left: stuck, write it at the end
- JFK has no tickets left: stuck, write it at the end
- ATL has no tickets left: stuck, write it at the end
- JFK has no tickets left: stuck, write it at the end
- Reversed post-order is the itinerary: JFK ATL JFK SFO ATL SFO
- Every ticket is used once; sorting costs O(E log E)
04Asked at Google
3 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.
| Problem | Difficulty | Frequency | Reported |
|---|---|---|---|
| Reconstruct Itinerary | Hard | 34 | last 6 months |
| Cracking the Safe | Hard | 22 | |
| Valid Arrangement of Pairs | Hard | 5 |
05Related patterns
Other patterns in Graphs: Grid flood fill (components), Multi-source BFS, BFS shortest path (unweighted), BFS over an augmented state, 0-1 BFS (deque), DFS three-colour cycle detection, Topological sort (Kahn's), Union–Find (disjoint sets), Dijkstra (weighted shortest path), Bellman–Ford with k rounds, Minimum spanning tree, Bipartite colouring, Bridges / articulation (low-link), Clone / traverse with a visited map, Implicit graph (states as nodes).