# LeetCode 332: Reconstruct Itinerary — Step-by-Step Visual Trace

**Hard** — Graph | Depth-First Search | Eulerian Path | Backtracking

## The Problem

Given a list of airline tickets represented as pairs of departure and arrival airports, return the itinerary in order starting from JFK, using all tickets exactly once.

## Approach

Build a graph from tickets sorted in reverse lexicographical order, then use DFS with Hierholzer's algorithm to find the Eulerian path. The algorithm uses a stack-based approach where we traverse as deep as possible and add nodes to the result in reverse order.

**Time:** O(E log E) · **Space:** O(E)

## Code

```python
class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        graph = collections.defaultdict(list)

        for start, end in sorted(tickets, reverse=True):
            graph[start].append(end)

        route = []

        def dfs(node):
            while graph[node]:
                dfs(graph[node].pop())
            route.append(node)

        dfs("JFK")

        return route[::-1]
```

## Watch It Run

> **[Open interactive visualization](https://tracelit.dev/app?trace=0332_reconstruct-itinerary)**

> **Try it yourself:** Open [TraceLit](https://tracelit.dev/app?trace=0332_reconstruct-itinerary) and step through every line.

---

*Built with [TraceLit](https://tracelit.dev) — the visual algorithm tracer for LeetCode practice.*