Reconstruct Itinerary

Reconstruct Itinerary looks like a sorting puzzle but is really a classic graph problem in disguise: finding an Eulerian path — a walk that uses every edge exactly once. The elegant solution is Hierholzer's algorithm.

The slow way first

The brute-force idea is backtracking: try every ticket out of the current airport, recurse, and undo if you get stuck before using all tickets. Because we want the smallest itinerary, you would sort the choices and take the first path that consumes every ticket. That works, but in the worst case it explores an exponential number of dead ends.

The question to ask: can I order my choices so I never have to backtrack? For this kind of "use every edge once" walk, there is a way — and it runs in linear time.

The idea: Hierholzer's algorithm

Build an adjacency list and sort each airport's destinations so the smallest is always tried first. Then run a DFS that greedily follows tickets. The twist is when we record an airport: we do not append it on the way in. We append it only when it has no outgoing tickets left — a dead end. As the recursion unwinds, each airport gets appended once its tickets are exhausted. That builds the route backwards, so we reverse it at the end.

Why does appending dead ends first work? A dead end in a directed Eulerian walk must be the end of the itinerary. By appending these terminal airports first and reversing, every airport lands in its correct final position automatically.

Walk through it

Step through the animation. From JFK we always take the smallest available ticket: JFK → ATL → JFK → SFO → ATL → SFO. SFO is the first airport with no tickets left, so it is appended first. As the recursion unwinds, the others append in reverse order. Finally we flip the list to read the itinerary forwards.

Pseudocode

build adjacency list; sort each airport's destination list
route = empty list
 
function dfs(airport):
    while airport still has tickets:
        next = remove the smallest destination of airport
        dfs(next)
    append airport to route        # only after its tickets are exhausted
 
dfs("JFK")
return route reversed

The Python solution

def find_itinerary(tickets):
    graph = defaultdict(list)
    route = []
    for src, dst in sorted(tickets):
        graph[src].append(dst)
 
    def dfs(airport):
        while graph[airport]:
            nxt = graph[airport].pop(0)
            dfs(nxt)
        route.append(airport)
 
    dfs("JFK")
    return route[::-1]

• We iterate sorted(tickets) so each airport's destination list is built in lexical order — the smallest is always at the front.
• graph[airport].pop(0) takes the smallest unused ticket and removes it, so it can never be reused.
• The while loop keeps diving until the airport has no tickets left.
• route.append(airport) runs after the loop — that is the Hierholzer move: an airport is recorded only once it is a dead end.
• route[::-1] reverses the back-to-front route into the final itinerary.

Complexity

Sorting the tickets costs O(E log E); the DFS then traverses each of the E edges exactly once. The space is O(E) for the adjacency list and recursion.

When this pattern shows up

Practice