← DSA Atlas
Dedicated problem page · #332

Reconstruct Itinerary

HardShortest Path, Dijkstra and Minimum Spanning TreeEulerian path (Hierholzer's algorithm)DFS with an edge stack
Solve on LeetCode ↗
332
HardShortest Path, Dijkstra and Minimum Spanning TreeDFS with an edge stackEulerian path (Hierholzer's algorithm)

Reconstruct Itinerary

You are given a list of airline tickets where tickets[i] = [from, to]. Reconstruct the itinerary that uses all tickets exactly once, starting from 'JFK'. If multiple valid itineraries exist, return the one with the smallest lexical order when read as a single string. A valid itinerary is guaranteed to exist.

Open official problem prompt ↗
In plain English

Order all the tickets into one continuous trip from JFK that uses each ticket exactly once and is lexicographically smallest.

Picture it like this

Like tracing a route through a subway map where you must ride every line exactly once; when you hit a station with no unridden lines left, you've found the tail end of your journey.

Example
Input
tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
Output
["JFK","MUC","LHR","SFO","SJC"]
Why
Starting at JFK, this is the only ordering that consumes every ticket exactly once.
Constraints
1 <= tickets.length <= 300tickets[i].length == 2from_i, to_i are 3 uppercase lettersfrom_i != to_iA valid itinerary using all tickets exists
Pattern lesson

See the pattern, then code

Eulerian path (Hierholzer's algorithm)
Recognition clue

Use every edge exactly once while forming a single path is the definition of an Eulerian path, solved with Hierholzer's algorithm.

↗
Shortest Path, Dijkstra and Minimum Spanning Tree

Shortest paths with non-negative weights or minimum-cost graph connection.. Greedily fly to the lexicographically smallest destination; when you get stuck (no outgoing tickets), that airport is the end of the trail, so prepend it. Building the route backward yields a valid Eulerian path.

New words, made simpleKnow these before the algorithm
Eulerian path
A walk that traverses every edge of a graph exactly once.
Hierholzer's algorithm
A method that builds an Eulerian trail by following edges until stuck, then splicing in cycles.
Lexical order
Dictionary order when comparing airport codes as strings.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Backtracking over all orderings

Exponential; times out on larger inputs.

Try each next ticket, backtrack if the full itinerary cannot be completed.

Time O(E!)Space O(E)
Best choiceHierholzer's algorithm

Linear-ish and always correct because a valid Eulerian path is guaranteed.

Greedily descend to smallest destinations; append dead-end nodes and reverse.

Time O(E log E)Space O(E)
The rule we keep true

Invariant

Every airport pushed back onto the route has no remaining unused outgoing tickets, so the reversed route consumes each edge exactly once.

Why this is correct

Reasoning

Sorting destinations descending and popping from the end makes the DFS always follow the smallest available edge first, guaranteeing lexical minimality. Hierholzer's post-order collection guarantees a valid Eulerian trail whenever one exists.

The algorithm in three movesSay these aloud before coding
1Build an adjacency list and sort each destination list

graph[JFK]=[MUC], graph[LHR]=[SFO]...

2Use a stack starting at JFK; always take the smallest unused outgoing ticket

stack drills JFK->MUC->LHR->SFO->SJC (dead end)

3When a node has no outgoing tickets left, pop it onto the route

pop dead ends, reverse -> itinerary

4Reverse the collected route to get the final itinerary

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
JFK0
MUC1
LHR2
SFO3
SJC4
1 · Read4 tickets
2 · AskNeighbors per node (desc-sorted)?
3 · Update stateJFK:[MUC], MUC:[LHR], LHR:[SFO], SFO:[SJC]
4 · ResultReady to walk
Key takeaway

The unique trail consuming all four tickets from JFK.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-5Build and sort graph

    Sorting tickets in reverse means each list, popped from the end, yields the smallest code first.

  2. 2
    Lines 6-7Init route and stack

    Stack simulates the DFS; route collects airports in reverse finishing order.

  3. 3
    Lines 8-11Drill down

    Keep advancing along the smallest unused ticket until the current airport is exhausted.

  4. 4
    Lines 12Record dead end

    An exhausted airport is prepended (via reversal) to the itinerary.

  5. 5
    Lines 13Reverse

    The post-order collection is backwards, so reverse it for the true itinerary.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • A single ticket -> [from, to]
  • Multiple tickets between the same pair of cities
  • Node revisited multiple times legitimately
  • A city that only appears as a destination (terminal)
!

Common beginner mistakes

  • Sorting ascending and popping from the front is O(n) per pop; sort descending and pop the tail instead
  • Collecting the route in forward order instead of reversing yields a broken path
  • Treating it as plain DFS without Hierholzer can get stuck and fail to use all tickets
Check your understanding

Why do we append an airport to the route only when it has no remaining outgoing tickets?

More in Shortest Path, Dijkstra and Minimum Spanning Tree

#743Network Delay TimeSingle-source shortest path#505The Maze IIWeighted shortest path on a grid#778Swim in Rising WaterMinimize the maximum along a path (minimax path)#787Cheapest Flights Within K StopsShortest path with a hop limit#815Bus RoutesUnweighted shortest path (fewest transfers)#1135Connecting Cities With Minimum CostMinimum spanning tree (Kruskal)