Reconstruct Itinerary
Use every airline ticket once to build the lexicographically smallest itinerary starting at JFK.
Open on LeetCode ↗Intuition
Greedily taking the smallest destination can enter a dead end before all tickets are used. The tickets are directed edges and the requested route uses every edge exactly once, so this is an Eulerian-path problem. Hierholzer's algorithm safely follows edges until stuck and records airports while backtracking. Choosing outgoing edges in lexical order produces the smallest valid itinerary.
The phrase 'use every ticket/edge exactly once' signals an Eulerian trail rather than ordinary path search. When lexical minimality is also required, order each vertex's outgoing edges while running Hierholzer's algorithm.
Approach
Store destinations as lexical min-heaps
For every ticket from -> to, push to into the heap for from. Tickets remain separate heap entries, so duplicate flights are preserved.
Consume an entire trail before recording its airport
DFS from JFK, repeatedly removing the smallest available outgoing ticket and recursing into its destination. Append the current airport only after it has no tickets left, which places dead ends at the correct suffix.
Reverse the postorder route
Postorder records the Eulerian path from end to start. Reverse it once to obtain the itinerary, with all tickets used exactly once and lexical choices resolved at each departure.
Solution
Common pitfalls
Appending before exploring
route.append(airport) visit(next_airport)
visit(next_airport) route.append(airport)
Eulerian construction records vertices on backtracking so premature dead ends land at the end.
Using a set for destinations
graph[source].add(destination)
heappush(graph[source], destination)
A set destroys duplicate tickets, even though each duplicate must be consumed.
Returning postorder directly
return route
return route[::-1]
Airports are appended from the route's end back toward JFK.
Edge cases
Each heap insertion is a separate edge and is popped exactly once.
Postorder insertion delays that dead end instead of invalidating the remaining tour.
DFS appends the destination then JFK, and reversal returns both airports.