Reconstruct Itinerary

Reconstruct Itinerary

What is this problem about?

The Reconstruct Itinerary problem gives you airline tickets as (from, to) pairs. Find the itinerary that uses all tickets, starts from "JFK", and is lexicographically smallest. This hard coding problem finds an Eulerian path in a directed multigraph using Hierholzer's algorithm. The Eulerian circuit, graph, and DFS interview pattern is the core.

Why is this asked in interviews?

Apple, Uber, Booking.com, Microsoft, Meta, Amazon, Google, Bloomberg, and many more ask this because it applies Eulerian path finding with lexicographic ordering — a combination of graph theory and greedy DFS. It tests deep graph algorithm knowledge beyond basic traversal.

Algorithmic pattern used

Hierholzer's algorithm (Eulerian path). Build adjacency list with sorted (lexicographic) neighbor lists. DFS from "JFK": for each node, visit neighbors in sorted order. When no unvisited neighbors remain, prepend the current node to the result. This naturally finds the lexicographically smallest Eulerian path.

Example explanation

tickets=[["JFK","MUC"],["MUC","JFK"],["JFK","LHR"],["LHR","JFK"]]. Sorted adj: JFK→[LHR,MUC], MUC→[JFK], LHR→[JFK]. DFS: JFK→LHR→JFK→MUC→JFK. Prepend at dead ends: [JFK,MUC,JFK,LHR,JFK]. Result: ["JFK","LHR","JFK","MUC","JFK"].

Common mistakes candidates make

• Using standard DFS without backtracking (leaves dead ends in wrong place).
• Not sorting adjacency lists (gives non-lexicographic result).
• Using pop from front instead of back (must remove from front for sorted order → use sorted list's first).
• Not understanding why post-order DFS gives the correct result.

Interview preparation tip

Reconstruct Itinerary uses Hierholzer's algorithm: post-order DFS on sorted neighbors, prepending nodes to result. The post-order ensures that dead-end branches are correctly inserted into the path. Practice finding Eulerian paths/circuits in undirected and directed graphs. The sorted adjacency list guarantees lexicographic ordering.