Reconstruct Itinerary

How it works

This is the iterative version of Hierholzer’s Algorithm for finding an Eulerian Path.

We must:

• use every ticket exactly once,
• start from "JFK",
• and return the lexicographically smallest valid itinerary.

Instead of recursion, we simulate the DFS using a stack:

• Keep moving forward while tickets exist.
• When stuck (no outgoing flights), backtrack and record the airport.

Key idea:

Airports are added to the answer only when they have no remaining outgoing edges.

Steps

1. Build an adjacency list from tickets.
2. Sort tickets in reverse lexicographical order so popping gives the smallest destination.
3. Initialize a stack with "JFK".
4. While the stack is not empty:
   • Look at the top airport:
     • If it has outgoing flights, pop one and push the destination.
     • Otherwise, pop the airport and add it to the result.
5. Reverse the result to get the final itinerary.

Complexity

• Time complexity: O(Elog E)
• Space complexity: O(E)

Where E is the number of tickets (edges) and V is the number of airports (vertices).

Things to watch for

Not Starting from JFK

The problem explicitly states the journey must begin from "JFK". Forgetting to initialize the traversal from "JFK" or accidentally starting from a different airport will produce an invalid itinerary.

Forgetting to Use Each Ticket Exactly Once

Each ticket represents a one-time-use flight. Failing to remove or mark tickets as used after consuming them leads to infinite loops or itineraries that reuse the same flight multiple times.

Sorting in Wrong Order for Hierholzer's Algorithm

Hierholzer's algorithm requires processing destinations in reverse lexicographical order (when using a stack/pop approach) so that popping gives the smallest destination. Sorting in ascending order without reversing, or using the wrong data structure, produces lexicographically incorrect results.

Not Reversing the Result in Post-Order Traversal

In Hierholzer's algorithm, airports are added to the result when backtracking (post-order), which builds the path in reverse. Forgetting to reverse the final result returns the itinerary in wrong order.

Confusing Dead Ends with Valid Endpoints

In the DFS backtracking approach, reaching an airport with no outgoing flights does not necessarily mean failure. It could be the valid end of the Eulerian path. Only return failure if you cannot use all tickets, not simply because you reached a node with no remaining edges.

from typing import List
from collections import defaultdict

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        adj = defaultdict(list)
        for src, dst in sorted(tickets)[::-1]:
            adj[src].append(dst)

        stack = ["JFK"]
        res = []

        while stack:
            curr = stack[-1]
            if not adj[curr]:
                res.append(stack.pop())
            else:
                stack.append(adj[curr].pop())

        return res[::-1]

class Solution {
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        unordered_map<string, vector<string>> adj;
        for (const auto& ticket : tickets) {
            adj[ticket[0]].push_back(ticket[1]);
        }
        for (auto& [src, destinations] : adj) {
            sort(destinations.rbegin(), destinations.rend());
        }

        vector<string> res;
        stack<string> stk;
        stk.push("JFK");

        while (!stk.empty()) {
            string curr = stk.top();
            if (adj[curr].empty()) {
                res.push_back(curr);
                stk.pop();
            } else {
                string next = adj[curr].back();
                adj[curr].pop_back();
                stk.push(next);
            }
        }

        reverse(res.begin(), res.end());
        return res;
    }
};