Reconstruct Itinerary - Solution & Explanation

Problem Overview: You receive a list of airline tickets where each ticket represents a directed edge [from, to]. Starting from "JFK", reconstruct the full travel itinerary that uses every ticket exactly once. If multiple valid routes exist, return the itinerary with the smallest lexical order.

The key observation: every ticket must be used exactly once, which turns the problem into finding an Eulerian path in a directed graph. Airports are nodes, tickets are edges. The itinerary is the path that visits every edge exactly once while respecting lexical ordering.

Approach 1: Hierholzer's Algorithm for Eulerian Path (O(E log E) time, O(E) space)

Model the tickets as a directed graph using an adjacency list. Because the itinerary must be lexicographically smallest, store each airport's destinations in sorted order (often implemented with a min-heap or reversed sorted list). Then run a depth-first traversal based on Hierholzer's algorithm. The DFS always takes the smallest available destination and removes that edge from the graph. When a node has no remaining outgoing edges, append it to the route. This naturally builds the itinerary in reverse order, so the final answer is reversed at the end. The algorithm works because Eulerian paths are constructed by exploring edges until a dead end, then backtracking while stitching partial circuits together. This is the most common interview solution and directly leverages concepts from graph traversal and Depth-First Search. Time complexity is O(E log E) due to sorting or heap operations, and space complexity is O(E) for the adjacency structure and recursion stack.

Approach 2: Iterative Stack-based Simulation (O(E log E) time, O(E) space)

This approach implements the same Eulerian path construction but avoids recursion. Instead of recursive DFS, maintain an explicit stack starting with "JFK". While the airport at the top of the stack still has outgoing flights, push the smallest destination onto the stack and remove that edge from the adjacency list. When an airport has no remaining outgoing edges, pop it from the stack and append it to the itinerary. This mimics the postorder behavior of DFS and constructs the path in reverse order, just like Hierholzer's algorithm. The iterative approach is useful in environments where recursion depth might be limited and gives more explicit control over the traversal state. The complexity remains O(E log E) time and O(E) space because edge ordering is still required.

Recommended for interviews: The Hierholzer DFS approach is what most interviewers expect because the problem is essentially an Eulerian path construction with lexical ordering. Showing that you recognize the graph structure and apply Hierholzer's algorithm demonstrates strong algorithmic understanding. The iterative stack version is a good follow-up optimization that shows you understand how DFS traversal works internally.