Reconstruct Itinerary — Hierholzer's Eulerian Path Algorithm [LC 332, Google, Meta, Amazon]

Problem Statement#

You are given a list of airline tickets tickets[i] = [from, to] representing one-way flights. Reconstruct the itinerary that uses every ticket exactly once. The traveller starts at "JFK". If multiple valid itineraries exist, return the one with the smallest lexicographic order when considered as a single string of airport codes.

Constraints:

• 1 <= tickets.length <= 300
• All airport codes are 3 uppercase letters.
• The input is guaranteed to allow at least one valid itinerary (Eulerian path exists).

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: ["JFK","SFO","ATL","JFK","ATL","SFO"] is also valid but
larger lexicographically.

Why This Problem Matters#

LeetCode 332 Reconstruct Itinerary is one of the most cited FAANG hard graph problems because it tests recognition of an Eulerian path under a deceptive prompt. Google, Meta, and Amazon all ask it, often as a follow-up to Word Ladder or Course Schedule, because solving it correctly proves you understand a non-obvious DFS pattern: post-order edge consumption.

Eulerian path / circuit problems are the algorithmic foundation behind DNA fragment assembly (de Bruijn graphs in bioinformatics), printer instruction routing, mail delivery scheduling, garbage collection routes, and circuit-board pen plotters that must trace each line exactly once. Whenever the problem is "use every edge once," reach for Hierholzer.

The interview signal here is high precisely because the wrong algorithms feel right but fail. Greedy "always pick the smallest next neighbour" works on most inputs but breaks when the smallest choice leads to a dead end with edges left unused. Pure backtracking works but is exponential. The clean linear-time answer is Hierholzer's algorithm with a small twist — append to the result in post-order, then reverse — which guarantees we never get stuck and respects lexicographic order.

The Core Insight#

An Eulerian path is a walk that uses every edge exactly once. It exists in a directed graph iff at most one vertex has out_degree - in_degree = 1 (the start) and at most one has in_degree - out_degree = 1 (the end), with all other vertices balanced and the graph connected when considering used edges.

Hierholzer's algorithm for directed graphs:

1. From the start vertex, run DFS.
2. From the current vertex u, repeatedly follow and remove the smallest unused outgoing edge until no edges remain.
3. When stuck (no edges left), append u to the result.
4. Backtrack to the previous vertex and continue.
5. Reverse the result.

The magic is in step 3. We add a node to the result only after all its outgoing edges are exhausted. If we hit a dead end, that node legitimately belongs at the end of the path; the recursion unwinds and we continue picking up the unused-edge cycles we skipped earlier. The reverse step gives the actual path order.

To enforce lexicographic order among valid itineraries, store outgoing edges in a min-heap (Python's heapq) or a sorted structure (Java's PriorityQueue, C++'s multiset). Always pop the smallest available next destination.

Time O(E log E) due to the heap; space O(V + E).

Visual Dry Run#

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

Adjacency (sorted): JFK -> [ATL, SFO], SFO -> [ATL], ATL -> [JFK, SFO].

DFS trace from JFK:

DFS(JFK)
  pop ATL, DFS(ATL)
    pop JFK, DFS(JFK)
      pop SFO, DFS(SFO)
        pop ATL, DFS(ATL)
          pop SFO, DFS(SFO)
            no edges -> append SFO
          append ATL
        append SFO
      append JFK
    append ATL
  append JFK

Result (post-order): [SFO, ATL, SFO, JFK, ATL, JFK]. Reverse: [JFK, ATL, JFK, SFO, ATL, SFO].

Notice the trick: at JFK we popped ATL (smaller than SFO) first. The recursion eventually returned to JFK and consumed the remaining SFO edge, but because JFK was appended only after both edges were exhausted, the post-order reversal places the second JFK correctly in the middle.

Solution (Optimal)#

Python — Hierholzer with min-heap#

import heapq
from collections import defaultdict
 
def findItinerary(tickets):
    adj = defaultdict(list)
    for src, dst in tickets:
        heapq.heappush(adj[src], dst)
 
    path = []
 
    def dfs(u):
        while adj[u]:
            v = heapq.heappop(adj[u])
            dfs(v)
        path.append(u)
 
    dfs("JFK")
    return path[::-1]

Python — iterative Hierholzer (avoids recursion)#

import heapq
from collections import defaultdict
 
def findItinerary(tickets):
    adj = defaultdict(list)
    for src, dst in tickets:
        heapq.heappush(adj[src], dst)
 
    stack = ["JFK"]
    path = []
    while stack:
        u = stack[-1]
        if adj[u]:
            stack.append(heapq.heappop(adj[u]))
        else:
            path.append(stack.pop())
    return path[::-1]

JavaScript — iterative Hierholzer#

function findItinerary(tickets) {
    const adj = {};
    for (const [s, d] of tickets) {
        if (!adj[s]) adj[s] = [];
        adj[s].push(d);
    }
    // sort descending so .pop() gives smallest
    for (const k of Object.keys(adj)) adj[k].sort().reverse();
 
    const stack = ["JFK"];
    const path = [];
    while (stack.length) {
        const u = stack[stack.length - 1];
        if (adj[u] && adj[u].length) {
            stack.push(adj[u].pop());
        } else {
            path.push(stack.pop());
        }
    }
    return path.reverse();
}

Complexity#

For E = 300, this is roughly 2400 operations — instantaneous.

Common Mistakes#

• Pure backtracking with recursion on every choice. Exponential time; will TLE on 300 tickets if you try it naively.
• Greedy smallest-next without recovery. Picks the smallest neighbour but gets stuck if that path is a dead end with unused edges remaining.
• Pre-order append instead of post-order. Adds a node before its edges are exhausted, producing an invalid order.
• Forgetting to reverse the result. Post-order naturally produces the reverse Eulerian path.
• Using a non-stable sort or wrong direction. In JavaScript, sorting with .sort() followed by .reverse() and using .pop() is the cleanest pattern.
• Mutating the heap during iteration without re-checking emptiness. Always re-check while adj[u] after the inner DFS returns.

Interview Tips#

• Open with the recognition: "We must use every edge exactly once. This is an Eulerian path problem; Hierholzer's algorithm solves it in O(E log E)."
• Justify the post-order trick: "If we naively pick the smallest neighbour first, we may dead-end. Post-order delays appending until all outgoing edges are consumed, which guarantees no dead-end edge is left behind."
• Show the iterative version if the input could be deep — recursion depth could reach E.
• Mention the lexicographic constraint affects only tie-breaking: Hierholzer's correctness does not depend on order; the heap is for ordering ties.
• For directed Eulerian, mention the existence conditions (at most one vertex with out-in degree 1, etc.) — useful follow-up signal.

Follow-up Questions#

• Eulerian circuit instead of path? Same algorithm but the start can be any vertex with non-zero out-degree, and the result must end where it started. Existence requires every vertex to have equal in and out degree.
• Undirected Eulerian path? Use a multiset of edges; remove each edge from both endpoints when traversed. Existence: exactly 0 or 2 vertices with odd degree.
• Find any Eulerian path, lexicographically smallest? Same algorithm; the heap enforces lex order.
• Chinese Postman problem? A generalisation: find the cheapest walk that uses every edge at least once. Reduces to T-join + matching when the graph is not Eulerian.
• De Bruijn sequence construction? Build a graph where vertices are length-(k-1) strings and edges are length-k strings; an Eulerian circuit yields the sequence.

Key Takeaways#

• LeetCode 332 Reconstruct Itinerary is an Eulerian path problem in disguise — every ticket = one directed edge.
• Hierholzer's algorithm builds the path in O(E log E) using DFS with post-order edge consumption, then reverses.
• Use a min-heap of outgoing destinations to enforce lexicographic order among valid itineraries.
• Pre-order append or naive greedy fails because dead-ends leave unused edges; post-order recovers them automatically.
• The same template solves Eulerian circuits, de Bruijn sequences, and DNA fragment assembly.
• Companies that ask this: Google, Meta, Amazon, Microsoft, Bloomberg, ByteDance, Stripe, Uber.