Reconstruct Itinerary (Graph & Stack)

To solve the Reconstruct Itinerary problem, I first visualize the tickets as a directed graph where each airport is a node and a ticket represents a directed edge. Since we need the smallest lexical itinerary, I will store the neighbors for each airport in a sorted data structure, like a priority queue or a sorted list, so we always visit the lexicographically smallest destination first. My approach uses Depth First Search with backtracking. The key insight is that we cannot simply add a node to our result when we first visit it; we might reach a dead end before using all tickets. Instead, I perform a DFS from JFK. For each current airport, I iterate through its available destinations in lexical order. If a destination exists, I remove that specific ticket (edge) and recursively visit the next airport. Crucially, I only add the current airport to my final itinerary list after the recursive call returns. This post-order traversal ensures that we have exhausted all possible paths from a node before committing it to the route. Once the recursion unwinds completely, the list will contain the correct itinerary in reverse order, which I then reverse to get the final answer. This handles the Eulerian path requirement naturally. Regarding complexity, sorting takes O(E log E), and the DFS visits each edge once, making the total time complexity efficient enough for large inputs.