Graphs crash course ↗ · 102

332. Reconstruct Itinerary

Given a list of airline tickets, reconstruct the itinerary starting from JFK that uses every ticket exactly once. If multiple valid orderings exist, return the one that is lexicographically smallest. Hierholzer's algorithm — DFS with post-order append and a final reverse — finds the Eulerian path in one linear pass.

● HardEulerian PathHierholzerDFSPost-orderTypeScript

PROBLEM What we're solving

Given a list of [from, to] airline tickets, find an itinerary that starts at JFK, uses every ticket exactly once, and is lexicographically smallest if multiple valid orderings exist.

Concrete example:
Tickets: [["JFK","MUC"],["MUC","LHR"],["LHR","SFO"],["SFO","SJC"]]
Expected output: ["JFK","MUC","LHR","SFO","SJC"]
There is only one valid Eulerian path here — follow the unique chain JFK → MUC → LHR → SFO → SJC.

KEY IDEA Euler path = DFS post-order + reverse

Insight → treat the tickets as a directed graph and find an Eulerian path(a path that visits every edge exactly once). Hierholzer's algorithm does this with a single DFS: always greedily take the smallest available destination, and push each airport onto the result after all its outgoing edges are consumed (post-order). Reversing the result gives the forward itinerary. The post-order trick handles dead-ends correctly — a dead-end airport is appended first, so after reversal it appears last.

RECIPE Sort → DFS → post-order push → reverse

1 · Build adjacency lists. For each [from, to] ticket, append to to adj[from]. Use a Map<string, string[]> so each airport stores its outbound destinations.
2 · Sort destinations ascending. Call dests.sort() on each list so we always try the lexicographically smallest neighbor first — this guarantees the smallest valid itinerary.
3 · DFS — consume destinations greedily. From the current airport, repeatedly shift() (remove) the smallest destination and recurse into it. Using shift() marks the edge as used so we never take it twice.
4 · Post-order push. After the while loop empties, push the current airport onto route. Airports with no remaining outgoing edges (dead-ends or the true tail) are appended first.
5 · Reverse. Because dead-ends get appended first, the array is backwards. route.reverse() produces the correct forward order.

Classic confusion → people try to build the result in pre-order (push before recursing) and then struggle when a greedy choice leads into a dead-end before all tickets are used. The fix is post-order: a dead-end node is safely pushed to the back of the reversed array, letting the algorithm backtrack implicitly via the call stack without explicit undo logic.

COST Complexity & alternatives

Backtracking (try all orderings)

O(E · E!)

Worst case: factorial permutations of tickets explored.

Hierholzer's (DFS + post-order)

O(E log E)

Dominated by the initial sort; DFS itself is O(E).

Space is O(E) for the adjacency lists and the recursion stack depth (at most E frames). The sort is the only non-linear cost; if the destinations were already sorted (or you used a min-heap), the DFS itself runs in O(E).

Pattern transfer →any "use every edge exactly once" prompt is an Eulerian path problem. The same post-order DFS pattern solves Cracking the Safe (LeetCode 753) and appears in Chinese Postmanrouting. It also generalizes to undirected Eulerian circuits (Fleury's algorithm) when the graph is undirected.

RUN IT Hierholzer: DFS post-order → reverse

tickets (FROM-TO,…)

step 0 / 15

STARTAdjacency lists built and sorted. Starting DFS from JFK.

1function findItinerary(tickets: string[][]): string[] {
2  // Build adjacency list: sorted in ascending (lexicographic) order per source
3▶  const adj = new Map<string, string[]>();
4▶  for (const [from, to] of tickets) {
5▶    if (!adj.has(from)) adj.set(from, []);
6▶    adj.get(from)!.push(to);
7▶  }
8▶  for (const dests of adj.values()) {
9▶    dests.sort();           // visit smallest destination first
10▶  }
11 
12  const route: string[] = [];
13 
14  function dfs(airport: string): void {
15    const dests = adj.get(airport);
16    while (dests && dests.length > 0) {
17      const next = dests.shift()!;   // consume smallest destination
18      dfs(next);
19    }
20    route.push(airport);             // post-order: push AFTER exhausting all departures
21  }
22 
23  dfs('JFK');
24  return route.reverse();            // reverse gives forward itinerary
25}

JFK→[MUC]LHR→[SFO]MUC→[LHR]SFO→[SJC]

State

{ JFK:[MUC], LHR:[SFO], MUC:[LHR], SFO:[SJC] }

adj

—

call stack

—

route (post-order)

current airportcall stackappended to route / resultnext destination (about to recurse)adjacency list state

slowfast

TYPESCRIPT The solution, annotated

findItinerary.ts
function findItinerary(tickets: string[][]): string[] {
  // Build adjacency list: sorted in ascending (lexicographic) order per source
  const adj = new Map<string, string[]>();
  for (const [from, to] of tickets) {
    if (!adj.has(from)) adj.set(from, []);
    adj.get(from)!.push(to);
  }
  for (const dests of adj.values()) {
    dests.sort();           // visit smallest destination first
  }

  const route: string[] = [];

  function dfs(airport: string): void {
    const dests = adj.get(airport);
    while (dests && dests.length > 0) {
      const next = dests.shift()!;   // consume smallest destination
      dfs(next);
    }
    route.push(airport);             // post-order: push AFTER exhausting all departures
  }

  dfs('JFK');
  return route.reverse();            // reverse gives forward itinerary
}

Reading it block by block

Lines 2–6 — build adjacency lists. Iterate every ticket and append the destination to adj[from]. The guard if (!adj.has(from)) adj.set(from, []) initializes the array on first encounter.

Lines 7–9 — sort destinations. dests.sort() on each adjacency list guarantees we always visit the lexicographically smallest neighbor first, which is what produces the smallest valid itinerary without any backtracking.

Lines 13–19 — DFS with consumption. The while loop dests.shift()s the smallest remaining destination and recurses. Using shift() removes the edge permanently so it cannot be taken twice.

Line 20 — post-order push. After exhausting all outgoing edges, route.push(airport) records this airport. Because dead-ends are exhausted first, they appear earliest in route — which is why we need the reverse.

Line 23 — start DFS and reverse. We kick off from "JFK" as guaranteed by the problem. After DFS completes, route.reverse() flips the post-order accumulation into the correct forward itinerary.

Complexity → O(E log E) time — the sort over all destinations dominates; the DFS itself visits each edge exactly once for O(E). Space is O(E) for adjacency lists and the recursion stack (depth at most E).

INTERVIEWFollow-ups they'll ask

"What if no valid itinerary exists?" The problem guarantees one exists. In general, an Eulerian path in a directed graph requires at most one node with out-degree − in-degree = 1 (start) and at most one with in-degree − out-degree = 1 (end); all others must be balanced.
"Why post-order and not pre-order?"Pre-order greedily appends the current node before recursing. If a greedy choice leads into a dead-end prematurely, the path is already "committed" and you'd need explicit undo. Post-order defers the append until after all edges are used, so the call stack handles backtracking implicitly.
"Can you do this iteratively?" Yes — replace the recursion with an explicit stack. Push airport; while stack is non-empty, if the top has neighbors, push the smallest neighbor (and remove it from adj); otherwise pop and append to route. Then reverse.
"What if tickets contain duplicate edges?" The algorithm handles duplicates naturally — each ticket is an independent edge, so JFK→A appearing twice simply means the JFK list contains two A entries, both consumed separately.
"Could you use a min-heap instead of a sorted array?" Yes. A min-heap (priority queue) lets you insert new edges in O(log E) and always extract the smallest in O(log E). For this problem the tickets are fixed upfront, so sorting once is simpler; a heap shines if edges arrive dynamically.

OPTIMAL Eulerian Path

findItinerary.ts
function findItinerary(tickets: string[][]): string[] {
  // Build adjacency list: sorted in ascending (lexicographic) order per source
  const adj = new Map<string, string[]>();
  for (const [from, to] of tickets) {
    if (!adj.has(from)) adj.set(from, []);
    adj.get(from)!.push(to);
  }
  for (const dests of adj.values()) {
    dests.sort();           // visit smallest destination first
  }

  const route: string[] = [];

  function dfs(airport: string): void {
    const dests = adj.get(airport);
    while (dests && dests.length > 0) {
      const next = dests.shift()!;   // consume smallest destination
      dfs(next);
    }
    route.push(airport);             // post-order: push AFTER exhausting all departures
  }

  dfs('JFK');
  return route.reverse();            // reverse gives forward itinerary
}

ALT 1 Backtracking DFS (sorted targets, return first complete path)

O(E^d) time worst case · O(E) space

Try each unused ticket in lexicographic order and backtrack whenever a branch cannot consume all tickets; the firstitinerary that uses every ticket is automatically the smallest, since we always explore smaller destinations first. It is slower than Hierholzer's because failed branches are unwound and retried instead of being threaded into one linear post-order walk.

approach-2.ts
function findItinerary(tickets: string[][]): string[] {
  // Build adjacency: each origin -> targets sorted lexicographically.
  const adj = new Map<string, string[]>();
  for (const [from, to] of tickets) {
    const list = adj.get(from);
    if (list) list.push(to);
    else adj.set(from, [to]);
  }
  for (const dests of adj.values()) {
    dests.sort();
  }

  // Track which tickets are still available via a "used" flag per slot.
  const used = new Map<string, boolean[]>();
  for (const [airport, dests] of adj) {
    used.set(airport, new Array<boolean>(dests.length).fill(false));
  }

  const totalTickets = tickets.length;
  const route: string[] = ['JFK'];

  function backtrack(airport: string): boolean {
    // A complete itinerary visits every ticket: route length = edges + 1.
    if (route.length === totalTickets + 1) return true;

    const dests = adj.get(airport);
    if (!dests) return false;
    const usedFlags = used.get(airport)!;

    for (let i = 0; i < dests.length; i++) {
      if (usedFlags[i]) continue;
      // Skip exploring an identical destination already tried at this depth,
      // so duplicate edges don't redo identical work.
      if (i > 0 && dests[i] === dests[i - 1] && !usedFlags[i - 1]) continue;

      usedFlags[i] = true;
      route.push(dests[i]);

      if (backtrack(dests[i])) return true; // first success is lexicographically smallest

      // Branch failed to use all tickets: undo and try the next target.
      route.pop();
      usedFlags[i] = false;
    }

    return false;
  }

  backtrack('JFK');
  return route;
}

Note → The optional duplicate-skip line (dests[i] === dests[i - 1]) is a small pruning that avoids re-exploring identical edges; remove it and the result is still correct, just slower on inputs with repeated tickets. Because targets are pre-sorted and we return on the first complete path, no explicit comparison of candidate itineraries is ever needed.

MNEMONIC The one-liner

"Sort the exits, walk to the dead-end, then stamp your passport on the way back out."

TRIGGERS When you see _ → reach for _

"use every ticket / edge exactly once"	Hierholzer Eulerian path DFS
lexicographically smallest valid ordering	pre-sort adjacency lists
greedy DFS hits dead-end before all edges used	post-order push + reverse
directed graph, all edges must be traversed	Eulerian path existence check

SKELETON The reusable shape

skeleton.ts
const adj = new Map<string, string[]>();
for (const [from, to] of tickets) {
  if (!adj.has(from)) adj.set(from, []);
  adj.get(from)!.push(to);
}
for (const dests of adj.values()) dests.sort();

const route: string[] = [];
function dfs(airport: string): void {
  const dests = adj.get(airport);
  while (dests && dests.length > 0) {
    dfs(dests.shift()!);
  }
  route.push(airport);   // post-order push
}
dfs('JFK');
return route.reverse();

FLASHCARDS Tap to flip

What algorithm reconstructs an Eulerian path on a directed graph?

Hierholzer's algorithm: DFS greedily consuming edges, post-order push, then reverse.

tap to flip

1 / 7

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

What is the time complexity of the Hierholzer solution with pre-sorted adjacency lists?

QUESTION 02

Why is the result built with route.push(airport) after the while loop, not before?

QUESTION 03

Trace the algorithm on tickets [["JFK","A"],["A","B"],["JFK","B"],["B","JFK"]]. What is the output?

QUESTION 04

Why must the adjacency lists be sorted before DFS rather than after?

QUESTION 05

What structure should you use for adjacency lists to allow O(1) edge removal from the front?

QUESTION 06

Which condition guarantees a directed graph has an Eulerian path (not necessarily circuit)?

QUESTION 07

What happens if you use a min-heap (priority queue) instead of a pre-sorted array for each adjacency list?

QUESTION 08

#332 · Reconstruct ItineraryHierholzer's algorithm for an Eulerian path: DFS with a lexicographically-sorted adjacency list (min-heap per airport), appending the current node to the route on the way back, then reverse.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Euler path = DFS post-order + reverse

RECIPE Sort → DFS → post-order push → reverse

COST Complexity & alternatives

RUN IT Hierholzer: DFS post-order → reverse

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL Eulerian Path

ALT 1 Backtracking DFS (sorted targets, return first complete path)

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _