Reconstruct Itinerary: Hierholzer's Eulerian Path

You are given a list of airline tickets as pairs [from, to]. Reconstruct the itinerary in order. All tickets must be used exactly once. The itinerary must begin at "JFK". If multiple valid itineraries exist, return the one with the smallest lexical order.

This is LeetCode 332: Reconstruct Itinerary, and it is secretly a graph problem dressed as a scheduling puzzle. The moment you see "use every edge exactly once," you are looking at an Eulerian path.

Why this problem matters

Most graph problems ask you to find the shortest path, detect a cycle, or check reachability. This one is different. You need to find a path that uses every single edge, not just some of them. That constraint changes the algorithm completely.

Eulerian path problems appear in surprisingly practical settings. Route optimization (covering every street in a city), circuit board tracing (connecting all points without lifting the pen), and DNA sequencing all reduce to finding an Eulerian path in some graph. Knowing Hierholzer's algorithm gives you a clean, generalizable tool for these situations.

In interviews, this problem separates candidates who just know DFS from candidates who understand graph structure. The key insight is not obvious on first read, and the implementation has a subtle trap that catches almost everyone the first time.

The key insight

You have a directed multigraph. Each ticket is a directed edge. You need to find a path that starts at "JFK" and uses every edge exactly once. That is the definition of an Eulerian path.

Use Hierholzer's algorithm:

1. Build an adjacency list. Sort each neighbor list so the smallest destinations come first.
2. Run DFS from "JFK". Always pick the next neighbor by popping from the front of the sorted list.
3. Append to the result in post-order: only after all of a node's outgoing edges have been used.
4. Reverse the result.

The post-order step is the heart of the algorithm. Here is why it works.

Why post-order?

Imagine you are at JFK and you greedily fly to the first available destination. You keep going until you reach a dead end. If you still have unused tickets, you got stuck down a wrong branch. You need to backtrack.

Hierholzer's algorithm handles this elegantly. Instead of trying to detect when you have gone down a bad branch, you always append a node to the result only after all of its outgoing edges have been exhausted. This means nodes that form dead ends get appended first. When you reverse the result at the end, those dead-end nodes end up at the back of the itinerary, which is exactly where they belong.

You do not need to detect or handle backtracking explicitly. The post-order insertion does it for you.

The Python solution

from collections import defaultdict

def findItinerary(tickets: list[list[str]]) -> list[str]:
    graph = defaultdict(list)
    for src, dst in sorted(tickets, reverse=True):
        graph[src].append(dst)
    result = []

    def dfs(airport):
        while graph[airport]:
            dfs(graph[airport].pop())
        result.append(airport)

    dfs("JFK")
    return result[::-1]

Why sort in reverse and use pop()?

You want to always visit the lexicographically smallest destination first. If you sort the tickets in reverse alphabetical order and then append destinations to each adjacency list, the smallest destination ends up at the end of the list. pop() removes from the end in O(1). If you sorted normally and used pop(0) to take from the front, each call would be O(n) because Python lists shift all elements left. Sort once in reverse, then pop() for O(1) per step.

This is the trick that catches people. pop(0) works but is slow. pop() with a reversed sort is the clean solution.

Why while graph[airport] instead of for?

The adjacency list shrinks as you pop edges. A for loop iterates over a fixed snapshot. The while loop correctly reads the shrinking list and stops when all edges from a node are used.

Step-by-step trace

Watch Hierholzer's algorithm run through the 5-ticket example. Notice how nodes only enter the result after all their outgoing edges are gone.

The reversal at the end is not a hack. It is the algorithm. You build the path backwards by post-order insertion, then flip it.

Complexity analysis

E is the number of tickets (edges).

The sort dominates. Each edge is visited exactly once during DFS (you pop it and never see it again), so traversal is O(E). The result list and the adjacency lists each hold E entries total, so space is O(E). The call stack depth is at most E in the worst case (a straight chain of airports).

Building blocks

This problem is built on four reusable pieces:

1. Eulerian path existence. A directed graph has an Eulerian path if and only if at most one node has out_degree - in_degree = 1 (the start) and at most one node has in_degree - out_degree = 1 (the end), and all other nodes are balanced. The problem guarantees a valid itinerary exists, so you do not need to check this.

2. Hierholzer's algorithm. DFS that builds the path in post-order. Works on both directed and undirected graphs. The reversal at the end converts the post-order sequence into the correct forward path.

3. Adjacency list with sorted neighbors. The standard representation for graph problems where you need to control traversal order. Sorting in reverse and using pop() is the O(1) trick.

4. Post-order DFS. The pattern of doing work after all recursive calls return. You see this in tree serialization, topological sort (DFS variant), and anywhere you need to process a node after all its descendants.

Edge cases

Single ticket. [["JFK", "ATL"]] returns ["JFK", "ATL"]. The DFS immediately hits a dead end at ATL and appends both airports.

Multiple tickets from the same source. The sorted adjacency list handles this. You always pop the lexicographically smallest option first.

Guaranteed valid answer. The problem states the input is always solvable. You do not need to check whether an Eulerian path exists, handle disconnected components, or return an error case. Every test case has at least one valid itinerary.

Self-referential airport. A ticket like ["JFK", "JFK"] is valid. The while loop handles it: when you are at JFK, you pop JFK, recurse into JFK again, and the inner call eventually exhausts its edges.

The trick that catches people

The most common mistake is using pop(0) instead of pop(). Both give you the correct answer, but pop(0) is O(n) per call. With up to 300 tickets, that is 300 calls each costing up to O(300), giving O(90,000) operations just for popping. It usually passes weak test cases but fails on large inputs.

The fix: sort in reverse once upfront, then pop from the end every time. The end of a reversed-sorted list is always the lexicographically smallest element.

# Slow: O(n) per pop
for src, dst in sorted(tickets):
    graph[src].append(dst)
graph[airport].pop(0)  # O(n)

# Fast: O(1) per pop
for src, dst in sorted(tickets, reverse=True):
    graph[src].append(dst)
graph[airport].pop()   # O(1)

Same result. One is a linear scan per call; the other is constant time.

From understanding to recall

You understand the post-order logic. You see why reversing works. The sorted(tickets, reverse=True) and pop() trick makes sense now. But can you write this from scratch in five minutes?

The danger is that this solution looks short but has several non-obvious details: the reversed sort, the while loop instead of for, the post-order result.append, and the [::-1] reversal. Each one is easy to forget under pressure.

Spaced repetition fixes this. You practice writing the dfs function from memory at increasing intervals. After a few rounds, you no longer need to derive why the reversal works. Your hands just write result.append(airport) after the while loop without thinking about it.

Related posts

• Course Schedule - directed graph cycle detection, builds the same graph traversal intuition
• Course Schedule II - topological sort on a directed graph
• Clone Graph - DFS/BFS on graph with adjacency lists

CodeBricks breaks Reconstruct Itinerary into its Eulerian path intuition, Hierholzer's post-order DFS, and sorted-adjacency-list building blocks, then drills them independently with spaced repetition. When this problem appears in your interview, you do not re-derive the algorithm. You just write it.