332. Reconstruct Itinerary

Q: Why DFS post-order specifically?

Because post-order naturally handles the dead-end case. If you recurse into a path that ends in a dead-end node (no remaining outgoing tickets), that node gets pushed first. The REST of the path — which still has unused edges — gets pushed later and ends up in front of the dead-end node after reversal. The post-order push is the entire algorithmic trick of Hierholzer's.

Q: Why sort destinations descending?

Because we want to consume the lex-smallest unused destination next. If the array is sorted DESCENDING, the lex-smallest sits at the END, where `.pop()` is O(1). Sorting ascending would force you to `.shift()` (O(n)) or maintain a pointer.

hardAsked at Cisco

Reconstruct Itinerary at Cisco is the Eulerian path problem — you must use every edge exactly once and return the path in lex-smallest order. The interviewer is checking whether you reach for Hierholzer's algorithm and whether you build the adjacency lists as sorted heaps or sorted arrays consumed back-to-front.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-19

Source citations

Public interview reports confirming this problem appears in Cisco loops.

Glassdoor (2026-Q1)— Cisco SDE-III onsite reports cite this as a hard graph round, often appearing in network-routing-team interviews.
Blind (2025-08)— Cisco interview thread lists Reconstruct Itinerary as a harder follow-up after standard graph questions.

Problem

You are given a list of airline tickets where tickets[i] = [fromi, toi] represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it. All of the tickets belong to a man who departs from 'JFK', thus, the itinerary must begin with 'JFK'. If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once.

Constraints

1 <= tickets.length <= 300
tickets[i].length == 2
fromi.length == 3
toi.length == 3
fromi and toi consist of uppercase English letters.
fromi != toi

Examples

Example 1

Input

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

Output

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

Example 2

Input

tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]

Output

["JFK","ATL","JFK","SFO","ATL","SFO"]

Explanation: Another valid itinerary ["JFK","SFO","ATL","JFK","ATL","SFO"] is rejected because it is larger in lexical order.

Approaches

1. Brute-force: DFS with backtracking

Build adjacency lists sorted lex. DFS from JFK trying each outgoing ticket. Backtrack on dead end. Stop the first time we use all tickets.

Time: O(E^d) worst case
Space: O(E)

function findItineraryBrute(tickets) {
  const graph = new Map();
  for (const [from, to] of tickets) {
    if (!graph.has(from)) graph.set(from, []);
    graph.get(from).push(to);
  }
  for (const list of graph.values()) list.sort();
  const totalEdges = tickets.length;
  const path = ['JFK'];
  function dfs() {
    if (path.length === totalEdges + 1) return true;
    const node = path[path.length - 1];
    const dests = graph.get(node) || [];
    for (let i = 0; i < dests.length; i++) {
      const next = dests[i];
      dests.splice(i, 1);
      path.push(next);
      if (dfs()) return true;
      path.pop();
      dests.splice(i, 0, next);
    }
    return false;
  }
  dfs();
  return path;
}

Tradeoff: Correct but exponential worst case. The splice/insert pair is what makes it backtracking — we 'consume' a ticket on the recurse and restore it on return. Cisco interviewers accept this; the optimal is Hierholzer's which avoids the backtracking.

2. Hierholzer's algorithm (optimal)

Build adjacency lists sorted lex. DFS post-order: when you can't recurse further, prepend the current node to the result. Reverse at the end.

Time: O(E log E)
Space: O(E)

function findItinerary(tickets) {
  const graph = new Map();
  for (const [from, to] of tickets) {
    if (!graph.has(from)) graph.set(from, []);
    graph.get(from).push(to);
  }
  // Sort descending so .pop() gives lex-smallest in O(1)
  for (const list of graph.values()) list.sort((a, b) => b.localeCompare(a));
  const result = [];
  function dfs(node) {
    const dests = graph.get(node) || [];
    while (dests.length) {
      const next = dests.pop();
      dfs(next);
    }
    result.push(node);
  }
  dfs('JFK');
  return result.reverse();
}

Tradeoff: Hierholzer's is the textbook Eulerian-path algorithm. The trick — sort destinations DESCENDING so `.pop()` is O(1) AND gives the lex-smallest unused edge. The post-order push handles the 'dead-end' case automatically — dead-ends get added to result first, then the rest of the path attaches in front of them.

Cisco-specific tips

Cisco interviewers grade this on whether you recognize the Eulerian-path structure. State out loud: 'Every ticket is an edge; we must traverse each edge exactly once = Eulerian path. The standard algorithm is Hierholzer's: DFS post-order, then reverse.' That sentence is the entire interview signal. The 'sort descending so pop is O(1)' trick is the optimization Cisco specifically rewards.

Common mistakes

Forgetting to REVERSE the result — post-order builds the path backward, and you have to flip it at the end.
Sorting destinations ASCENDING and using `shift()` instead of `pop()` — correct but O(n) per op, blowing up to O(n^2) total.
Using BFS — Eulerian-path needs DFS post-order specifically, not breadth-first.

Follow-up questions

An interviewer at Cisco may pivot to one of these next:

Eulerian circuit (closed Eulerian path) — only changes the input requirement (every node has equal in/out degree), same algorithm.
What if the graph might NOT have an Eulerian path? (Check in/out degree parity per node before starting.)
Chinese Postman Problem — variant where you can repeat edges to find the shortest tour.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why DFS post-order specifically?

Because post-order naturally handles the dead-end case. If you recurse into a path that ends in a dead-end node (no remaining outgoing tickets), that node gets pushed first. The REST of the path — which still has unused edges — gets pushed later and ends up in front of the dead-end node after reversal. The post-order push is the entire algorithmic trick of Hierholzer's.

Why sort destinations descending?

Because we want to consume the lex-smallest unused destination next. If the array is sorted DESCENDING, the lex-smallest sits at the END, where `.pop()` is O(1). Sorting ascending would force you to `.shift()` (O(n)) or maintain a pointer.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Reconstruct Itinerary and other Cisco interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →