Reconstruct Itinerary

You are given a list of airline tickets where:

tickets[i] = [from, to]

Each ticket represents a flight from one airport to another.

All tickets belong to one traveler who starts at:

JFK

You must reconstruct the complete itinerary.

Rules

• The itinerary must start from JFK.
• Every ticket must be used exactly once.
• If multiple valid itineraries are possible, return the one with the smallest lexical order.

Example

tickets =

[

    ["MUC","LHR"],

    ["JFK","MUC"],

    ["SFO","SJC"],

    ["LHR","SFO"]

]

The itinerary is:

JFK → MUC → LHR → SFO → SJC

So the answer is:

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

Main Idea

This is a Graph + DFS + Eulerian Path problem.

Think of:

Airport → Node

Ticket  → Directed Edge

For example:

JFK → MUC

MUC → LHR

LHR → SFO

SFO → SJC

The important part is that every ticket must be used exactly once.

So this is an Eulerian Path problem.

Approach

1. Build an adjacency list.
2. Sort destinations lexicographically.
3. Start DFS from JFK.
4. Always choose the smallest available destination.
5. Remove a ticket when using it.
6. If an airport has no unused tickets left, add it to the answer.
7. Reverse the resulting route.

Why postorder?

Consider:

JFK → A

JFK → B

A → JFK

Simply choosing the smallest destination greedily can lead to a dead end.

DFS handles this by adding an airport to the result only after all its outgoing tickets have been used.

This is the key idea behind Hierholzer's Algorithm.