Reconstruct Itinerary
You are given a list of airline tickets as [from, to] pairs. Starting at JFK, build an itinerary that uses every ticket exactly once. If several itineraries are possible, return the one that is lexicographically smallest when read as a sequence of airports.
- 1 ≤ tickets.length ≤ 300
- Airport codes are 3 uppercase letters
- At least one valid itinerary exists
- Use every edge exactly once — an Eulerian path
- Lexicographic order → sort each adjacency list
- Hierholzer: append a node when it has no unused edges left
DFS follows one branch to exhaustion before backtracking, which makes it the natural tool for "which cells/nodes belong together", for enumerating complete paths, and for cycle detection via the recursion stack (gray nodes). It needs only the graph plus a visited set and is easily written recursively.
Build an adjacency map with each destination list sorted (or a min-heap). Run Hierholzer's algorithm: from JFK, repeatedly take the smallest unused outgoing edge and recurse; when a node has no remaining edges, append it to the route. Reverse the route at the end. Post-order appending guarantees that dead ends are placed last, producing a valid Eulerian path that respects the sorted choices.
- Backtracking that tries tickets in sorted order and undoes choices is correct but can be exponential in adversarial cases; Hierholzer never backtracks.