Hey everyone! 👋

I’ve been grinding through the Google Spring '23 High Frequency study plan recently. After solving a few complex graph problems, I wanted to share a quick breakdown of how to think about Depth-First Search (DFS) and Breadth-First Search (BFS)—especially in the context of top-tier company interviews.

If you are prepping for Google, graph traversal is non-negotiable. Here is how I break it down:

🗺️ The Case Study: Reconstruct Itinerary (Problem 332)
This problem is a phenomenal example of why picking the right traversal method matters. At first glance, you might think of trying various paths, but it's actually a classic Eulerian Path problem.

Why DFS was the winner here:

1.Hierholzer's Algorithm: By using a post-order DFS, we can dive deep into the graph, continuously picking the lexicographically smallest destination (using a Min-Heap/Priority Queue).

2.The "Stuck" Condition: DFS naturally handles the core logic of this problem. When a node (airport) has no outgoing edges left, we get "stuck." In post-order DFS, getting stuck just means we've reached the end of our current path, so we append the node to our itinerary and backtrack.

3.Reversing the result at the end gives us the perfect chronological path!

⚖️ DFS vs. BFS: The Ultimate Cheat Sheet
When you see a graph or matrix problem in an interview, how do you instantly know which one to use?

Use Breadth-First Search (BFS) when:

1.Shortest Path in an Unweighted Graph: If the question asks for the "minimum steps," "shortest distance," or "closest target," BFS is your best friend. It explores evenly in all directions (level by level).

2.Level-Order Traversal: Any time you need to process a tree or graph level by level (e.g., "Rotting Oranges" or "Word Ladder").

3.Data Structure: Queue (FIFO).

Use Depth-First Search (DFS) when:

1.Exhaustive Search / Backtracking: When you need to explore all possible paths or combinations (e.g., generating permutations, solving mazes).

2.Topological Sorting & Eulerian Paths: Like in the Reconstruct Itinerary or Course Schedule problems, where the order of visits relies on exploring a full branch first.

3.Connectivity / Islands: Counting connected components (like "Number of Islands") is often cleaner to write recursively with DFS.

4.Data Structure: Stack (LIFO) or Recursion (Call Stack).

💡 Takeaway
Don't just memorize the algorithms; understand the shape of the search space they create. Google interviewers love it when you explicitly state why you are choosing DFS over BFS before you write a single line of code.

What is your favorite DFS or BFS problem on LeetCode? Let me know in the comments, I'm looking to add a few more to my list! Happy coding! 💻✨