Reconstruct Itinerary LeetCode 332 Guide

LeetCode 332 — Reconstruct Itinerary — gives you a list of airline tickets represented as pairs [from, to]. You must reconstruct the itinerary using all tickets exactly once, starting from "JFK". If multiple valid itineraries exist, return the one with the lexicographically smallest order.

Each ticket is a directed edge in a graph. The problem guarantees that a valid itinerary always exists — meaning the graph is guaranteed to have an Eulerian path starting from JFK. You must use every ticket (every edge) exactly once.

The challenge is that naive backtracking explores exponentially many orderings. The efficient solution uses a classical graph theory algorithm — Hierholzer's algorithm for Eulerian paths — which runs in O(E log E) time.

An Eulerian path is a trail in a graph that visits every edge exactly once. An Eulerian circuit visits every edge exactly once and returns to the starting vertex. The requirement to use all tickets exactly once and start from JFK is precisely the definition of an Eulerian path starting at JFK.

For a directed graph, an Eulerian path exists when the graph is connected and either all nodes have equal in-degree and out-degree (Eulerian circuit), or exactly one node has out-degree − in-degree = 1 (start node) and exactly one node has in-degree − out-degree = 1 (end node), with all other nodes balanced. The problem guarantees this condition holds.

Recognizing this as an Eulerian path problem is the key that unlocks the efficient solution. Without this insight, you might attempt DFS with backtracking, which works but is exponential in the worst case. Hierholzer's algorithm solves it in linear time by exploiting the Eulerian path structure.

Hierholzer's algorithm finds an Eulerian path by performing a modified DFS. Build an adjacency list where each node's destinations are sorted in lexicographic order (to ensure the result is lexicographically smallest). Start DFS from JFK.

During DFS, when a node has no more unvisited outgoing edges (its adjacency list is empty), add it to the result list. This is post-order insertion — the node is recorded after all its outgoing paths have been exhausted. At the end, reverse the result list to get the correct itinerary order.

The reversal is necessary because the algorithm records nodes as they are finished (no more outgoing edges), which is the reverse of the actual traversal order. The first node added to the result is actually the last in the itinerary, and reversing corrects this.

The core idea of Hierholzer's algorithm is that nodes are added to the path in post-order — after all their outgoing edges have been visited. When the DFS backtracks from a dead end, that dead-end node is placed at the current tail of the result. Reversing at the end moves it to its correct position: the tail of the itinerary.

Consider a graph where JFK goes to two destinations: A (which leads nowhere) and B (which leads back through a long chain ending at A). A greedy DFS visiting A first gets stuck immediately, but Hierholzer handles this correctly: it visits A, records it (dead end), backtracks to JFK, then visits B and completes the rest of the chain.

The beauty of post-order insertion is that it naturally handles dead-end branches: dead ends get recorded first, appear last in the reversed list (i.e., at the end of the itinerary), which is exactly where dead ends should be — at the destination of the trip.

To return the lexicographically smallest itinerary, the key is to always visit the smallest destination first when multiple options exist from any given node. This is achieved by sorting each adjacency list alphabetically before starting the DFS.

In Python, use a collections.defaultdict(list) to build the adjacency list, then sort each list. During DFS, pop from the front of the sorted list (using popleft on a deque) or use heapq.heappop if using a min-heap. Each pop removes the destination so it cannot be reused.

In Java, use a HashMap with TreeMap or PriorityQueue as the value to maintain sorted order. Poll from the priority queue to always get the lexicographically smallest next destination. The sorted structure ensures the first valid itinerary found by DFS is the lexicographically smallest.

In Python, use defaultdict(list) to build the graph, sort each adjacency list, then convert to deque for O(1) popleft. DFS function: while graph[node] is non-empty, popleft the next destination and recurse. After the while loop, append node to result. Call dfs("JFK"), then return result reversed. Time: O(E log E) for sorting, O(V + E) for traversal. Space: O(V + E).

Alternatively in Python, use heapq: heapify each adjacency list, then heappop during DFS. This gives the same O(E log E) complexity and avoids the sort-then-deque conversion. In Java, use Map<String, PriorityQueue<String>> where the PriorityQueue maintains min-heap order. Poll from the queue during DFS and add the node to a LinkedList result, then reverse it.

Both implementations are clean and interview-ready. The Python deque approach is most readable; the heapq approach is slightly more idiomatic for competitive programming. In Java, PriorityQueue is the natural choice. All versions share the same post-order DFS structure: recurse first, append to result after — then reverse.

Reconstruct Itinerary belongs to the Eulerian path and graph traversal family. Alien Dictionary (topological sort) also requires ordering graph nodes subject to constraints, but uses BFS/DFS for DAG ordering rather than Eulerian path finding. Clone Graph is a fundamental DFS/BFS graph traversal problem where the structure mirrors the post-order node processing pattern.

Network Delay Time (LC 743) and Cheapest Flights K Stops (LC 787) share the directed weighted graph structure but focus on shortest paths rather than edge coverage. The common thread across all these problems is building an adjacency list and applying the right traversal strategy: Dijkstra for shortest path, topological sort for DAGs, and Hierholzer for Eulerian paths.

For broader interview preparation, recognizing problem families is key. When every edge must be visited exactly once, think Eulerian path and Hierholzer. When ordering nodes with dependencies, think topological sort. When minimizing cost across a graph, think Dijkstra or Bellman-Ford. Reconstruct Itinerary is the canonical Eulerian path problem in the LeetCode catalog.