06. Reconstruct Itinerary

Difficulty:HardPattern:Hierholzer Eulerian Path DFSTime:O(E log E)Space:O(V + E)

You are given a list of airline tickets where tickets[i] = [from_i, to_i]. Reconstruct the itinerary in order and return it. All tickets must be used, starting from 'JFK'. If there are multiple valid itineraries, return the itinerary that has the smallest lexical order.

How It Works & Algorithmic Design

Solves using Hierholzer's Eulerian Path DFS Algorithm:

Sorted Adjacency Map: Build directed graph using a Min-Heap/Priority Queue for destination neighbors to enforce lexicographical traversal.
Hierholzer's Post-Order DFS dfs(airport):
- While adj[airport] is not empty:
  - Pop smallest destination neighbor next = adj[airport].poll().
  - Recurse dfs(next).
- Push airport onto result stack.
Return: Reverse result stack.

Why This Approach Works Best

Hierholzer's algorithm traverses every graph edge (ticket) exactly once in $O(E \log E)$ time, handling back-tracking dead-ends naturally.

Example Walkthrough

Input: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]

Flight ticket pairs.

Eulerian Path: "JFK" -> "MUC" -> "LHR" -> "SFO" -> "SJC"

All tickets visited in order.

Output: ["JFK","MUC","LHR","SFO","SJC"]

Final itinerary.

Answer: Reconstruct Itinerary Hierholzer implementation

function findItinerary(tickets) {
  const adj = {};
  for (const [from, to] of tickets) {
    if (!adj[from]) adj[from] = [];
    adj[from].push(to);
  }
  for (const from in adj) adj[from].sort();
  const res = [];
  function dfs(airport) {
    const dests = adj[airport];
    while (dests && dests.length) {
      dfs(dests.shift());
    }
    res.push(airport);
  }
  dfs('JFK');
  return res.reverse();
}

💡 Traverse smallest airport neighbors via Eulerian path DFS and reverse accumulated post-order stack.

Key Takeaways

Guarantees all directed edges (tickets) are consumed exactly once.
Sorting airport neighbors satisfies smallest lexicographical choice requirement.
Reversing post-order traversal stack yields the correct path order.