Reconstruct Itinerary: the idea to remember.

The core insight

Consume the smallest available outgoing destination and append airports only after exhausting their outgoing edges.

Why it works

Reverse postorder stitches exhausted trails into a complete Eulerian path; ordered edge choices give the smallest valid itinerary.

The mistake to avoid

A greedy forward walk can get stuck early. Append on return and reverse the route at the end.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

// Java reference adapted from neetcode-gh/leetcode (MIT).
// Consume the smallest available outgoing destination and append airports only after exhausting their outgoing edges.
public List<String> findItinerary(List<List<String>> tickets) {
    LinkedList<String> itinerary = new LinkedList<>();
    Map<String, PriorityQueue<String>> graph = new HashMap<>();
    Stack<String> stack = new Stack<>();

    for (List<String> ticket : tickets) {
        graph
            .computeIfAbsent(ticket.get(0), k -> new PriorityQueue<>())
            .add(ticket.get(1));
    }

    stack.push("JFK");
    while (!stack.isEmpty()) {
        String nextDestination = stack.peek();

        if (
            !graph
                .getOrDefault(nextDestination, new PriorityQueue<>())
                .isEmpty()
        ) {
            stack.push(graph.get(nextDestination).poll());
        } else {
            itinerary.addFirst(stack.pop());
        }
    }
    return itinerary;
}

Java reference adapted from neetcode-gh/leetcode · MIT license

Make the next connection