#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/euler-paths-and-circuits/reconstruct-itinerary-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/euler-paths-and-circuits/reconstruct-itinerary-implementation

Repovive

Reconstruct Itinerary - Implementation - Euler Paths and Circuits | Graph Theory | Repovive

Repovive.

Graph Theory37 sections · 1633 units81h total

Open in Course

Reconstruct Itinerary - Implementation

Code walkthrough.

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.