Skip to main content

Pattern · 45 problems

BFS and DFS Interview Problems

Depth-first dives and backs out. Breadth-first spreads in rings. I pick by asking whether the first arrival must be the shortest.

Get the link for your laptop

Free: write the code and run it, no sign-up.

When I reach for it

  • You walk a grid, a graph or a tree and visit each cell once.
  • The word shortest appears and every step costs the same.
  • You count regions or connected pieces.

Problems, easiest first

7 easy · 29 medium · 9 hard. Open one to read it, then write it in the free editor.

  1. Same TreeeasyTrees
  2. Subtree of Another TreeeasyTreesStrings
  3. Maximum Depth of Binary TreeeasyTrees
  4. Invert Binary TreeeasyTrees
  5. Balanced Binary TreeeasyTrees
  6. Diameter of Binary TreeeasyTrees
  7. Flood FilleasyArrays & Hashing
  8. Clone GraphmediumGraphs
  9. Construct Binary Tree from Preorder and Inorder TraversalmediumTreesArrays & Hashing
  10. Kth Smallest Element in a BSTmediumTrees
  11. Lowest Common Ancestor of a Binary Search TreemediumTrees
  12. Number of Connected Components in an Undirected GraphmediumGraphs
  13. Word SearchmediumBacktrackingStrings
  14. Design Add and Search Words Data StructuremediumTreesDesign
  15. Binary Tree Level Order TraversalmediumTrees
  16. Coin ChangemediumDynamic ProgrammingArrays & Hashing
  17. Course SchedulemediumHeapsGraphs
  18. Graph Valid TreemediumGraphs
  19. Number of IslandsmediumGraphsArrays & Hashing
  20. Pacific Atlantic Water FlowmediumGraphsArrays & Hashing
  21. Validate Binary Search TreemediumTrees
  22. Binary Tree Right Side ViewmediumTrees
  23. Cheapest Flights Within K StopsmediumHeapsGraphs
  24. Count Good Nodes in Binary TreemediumTrees
  25. Course Schedule IImediumGraphs
Show the other 20 problems
  1. Max Area of IslandmediumGraphsArrays & Hashing
  2. Network Delay TimemediumHeapsGraphs
  3. Redundant ConnectionmediumGraphsArrays & Hashing
  4. Rotting OrangesmediumGraphsArrays & Hashing
  5. Surrounded RegionsmediumGraphsArrays & Hashing
  6. Walls and GatesmediumGraphsArrays & Hashing
  7. Accounts MergemediumGraphsStrings
  8. Distance to Nearest ZeromediumArrays & Hashing
  9. Minimum Height TreesmediumGraphs
  10. Lowest Common Ancestor of a Binary TreemediumTrees
  11. Web CrawlermediumGraphsDesign
  12. Binary Tree Maximum Path SumhardTreesDynamic Programming
  13. Serialize and Deserialize Binary TreehardTreesDesign
  14. Word Search IIhardBacktrackingTrees
  15. Alien DictionaryhardGraphsStrings
  16. Longest Increasing Path in a MatrixhardGraphsDynamic Programming
  17. Reconstruct ItineraryhardBacktrackingGraphs
  18. Swim in Rising WaterhardBinary SearchHeaps
  19. Word LadderhardGraphsStrings
  20. Trapping Rain WaterhardStackHeaps

The idea

Use breadth-first search when the first time you reach a cell is the shortest way there. Use depth-first search to cover a whole region or try every path.

Mark a cell visited when you queue it, not when you pop it. Otherwise the same cell enters the queue many times.

from collections import deque

queue = deque([start])
seen = {start}                        # mark on entry, not on exit
steps = 0
while queue:
    for _ in range(len(queue)):       # one ring at a time
        r, c = queue.popleft()
        if (r, c) == goal:
            return steps
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nxt = (r + dr, c + dc)
            if in_bounds(nxt) and nxt not in seen:
                seen.add(nxt)
                queue.append(nxt)
    steps += 1
return -1                             # the goal was never reached
Fewest steps across a grid. One ring of the queue is one step, and a cell is marked the moment it is queued. Python shown; the idea carries to every language in the editor.

Where it goes wrong

  • Recursing so deep that a big grid overflows the call stack.
  • Marking a cell visited too late.
  • Leaving out the bounds check at the edge of the grid.

Say this before you type. Say why breadth or depth fits, and exactly when a cell counts as visited.

Where Coco comes in

Coco is an AI study partner, not a person. She listens while you explain your code, asks what a line does and never hands you the fix. Sign in free to type with Coco, up to a daily limit, and to talk with her for one hour. After that, talking comes with the $79 pack. Anyone can open the editor and run their code.

Questions people ask

When does BFS beat DFS?
When every edge costs the same and you want the fewest steps. The first time breadth-first search reaches a node is the shortest way.
Do I need a visited set on a tree?
No. A tree has no cycles, so walking from parent to child reaches every node once. A grid or a graph does need one.

Meet these next

Fin and Coco are characters, not people. strongyes.io is independent. Leo builds it with AI agents.