BFS / DFS: how to spot it
We'll cover the following
Explore a tree, grid or graph. BFS uses a queue and goes level by level. DFS uses recursion or a stack and goes as deep as it can before backing up.
How the question sounds
- Level by level, or the shortest path when every step costs the same: BFS
- Count islands, flood fill, connected regions: DFS or BFS
- All paths, tree depth, validate a BST: DFS (recursion)
- The input is a tree, a grid or a graph
The two shapes
Where it shows up in GenAI work
Crawling pages to build a RAG corpus is BFS. Walking an agent's tool graph, a file tree, or a knowledge graph is DFS or BFS.
Is it bfs / dfs?
Decide yes or no before you open each answer.
Check yourselfFind the shortest path through a maze, moving in 4 directions.
Yes. Equal step costs and shortest path: BFS.
Check yourselfReturn a binary tree's values level by level.
Yes. Level by level is a queue.
Check yourselfCount the islands in a grid of land and water.
Yes. Flood-fill each unvisited land cell with DFS or BFS.
Check yourselfFind the maximum sum of a contiguous subarray.
No. A one-dimensional running total, which is Kadane's, a small DP.
Check yourselfCheck that brackets are balanced.
No. That is a stack, not a search over a graph.
Check yourselfFind two numbers in a sorted array that sum to a target.
No. Two pointers.
Problems in this pattern
- Level order traversal · Medium · BFS on a tree
- Maximum depth of a tree · Easy · DFS on a tree
- Number of islands · Medium · Flood fill
- Shortest path in a maze · Medium · BFS on a grid
Summary: say it in the interview
- BFS (queue): Visit everything one step away, then everything two steps away. First to reach the goal wins.
- DFS (stack): Follow one path to the end, then back up and try the next. Recursion is the easy way to write it.