Reconstruct Itinerary (LC 332)

LeetCode 332 verbatim: reconstruct a flight itinerary from a list of tickets, starting at JFK, lexicographically smallest when ties. Asked both as a phone-screen warmup and as an onsite coding round. The cycle-handling follow-up trips up candidates who only know the canonical Hierholzer solution. Requirements Given a list of airline tickets [from, to], reconstruct the itinerary starting at JFK that uses every ticket exactly once. If multiple valid itineraries exist, return the lexicographically smallest one when read as a single string. Follow-up: handle the case where the ticket graph contains a cycle (the route revisits a city). Examples The canonical LeetCode 332 examples apply; interviewers do not introduce a Pinterest-specific framing. Notes The standard solution is Hierholzer's algorithm for Eulerian path: DFS where each city's outbound destinations are kept in a min-heap; on each recursive return, prepend the city to the itinerary. This handles cycles correctly without special casing. A naive backtracking approach (try lexicographically-smallest next ticket; backtrack if the recursion dead-ends) also passes and is what most candidates write first. Be prepared to defend the worst-case complexity — O(E^d) for backtracking vs O((V + E) log E) for Hierholzer. The cycle follow-up is where candidates stall: Hierholzer naturally handles cycles, but candidates who wrote the greedy-with-no-backtrack version (which is incorrect even on the base problem) cannot patch it for cycles. The fix is to backtrack or to switch to Hierholzer. The canonical problem has small input bounds (up to 300 tickets), which is why backtracking with no memoization passes — the search tree is heavily pruned by the use-each-ticket-once constraint. A frequent interviewer push: "can you do this iteratively?" — yes, with an explicit stack mirroring the recursive DFS. Practice the iterative version once; it doubles as the answer to "what if the recursion depth blows the stack". Preparation Implement Hierholzer once from scratch (min-heap per node, DFS, post-order append) and explain why the post-order produces the path in correct order. Drill the iterative version with an explicit stack — interviewers occasionally ask for it as a follow-up. Practice the cycle test case (e.g., JFK → A → B → A → C) by hand to make sure your implementation handles revisits without infinite-looping.