Reconstruct Itinerary - Implementation

function reconstructItinerary(tickets):
    adj = map from string to sorted list
    for each ticket [from, to]:
        adj[from].append(to)
        for each airport in adj:
            sort adj[airport]

            result = []

function dfs(airport):
    while adj[airport] not empty:
        next = adj[airport].pop_front()
        dfs(next)
        result.append(airport)

        dfs("JFK")
        return result.reversed()

Note: Use a deque or similar structure for efficient front removal, or iterate with an index.

This runs in $O(E \log E)$ time and uses $O(E)$ space.