MediumDSA14 min read

What is the difference between BFS and DFS?

Q: What is the difference between BFS and DFS?

**Target Audience:** Beginners preparing for coding interviews — you should know what a graph and an adjacency list are **Difficulty:** Medium **Language:** Python 3 > **How to read this doc:** every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged `📌 Interview term:` with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output you see in the **Verified** section is copied from that run. ## 1. Why This Even Matters — A Story First You have lost your cat somewhere in a big old house. Two friends offer to help, and they search in completely different styles. **Friend one** stands in the hallway and checks every room that opens off the hallway first. Only when all of those are done does she check the rooms that open off *those* rooms, and so on, spreading outwards like a ripple on a pond. If the cat is two doors away,

525 views

85 of 154

The problem

Question presented to candidate: "Explain the difference between breadth-first search and depth-first search on a graph. Then implement both in Python and tell me when you would choose one over the other."

What a strong answer should cover:

The one structural difference: BFS uses a FIFO queue, DFS uses a LIFO stack (or recursion).
Visit order: BFS goes level by level, DFS goes deep then backtracks; both need a visited set for cycles.
Both are O(V + E) time; memory is the widest level for BFS and the deepest path for DFS.
BFS gives shortest paths in unweighted graphs; DFS does not. Typical uses of each (topological sort, cycle detection, backtracking vs nearest/minimum steps).
Python details: collections.deque with popleft() (not list.pop(0)), and the default recursion limit of 1000 that breaks recursive DFS on deep graphs.

Code / implementation expected: Yes — BFS with deque and DFS both recursively and with a list used as a stack, in Python.

graphs
bfs
dfs

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners preparing for coding interviews — you should know what a graph and an adjacency list are
Difficulty: Medium
Language: Python 3

How to read this doc: every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged 📌 Interview term: with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output you see in the Verified section is copied from that run.

1. Why This Even Matters — A Story First

You have lost your cat somewhere in a big old house. Two friends offer to help, and they search in completely different styles.

Friend one stands in the hallway and checks every room that opens off the hallway first. Only when all of those are done does she check the rooms that open off

The solution is hidden so you can try first

14 min read · 12 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonBFS order and distances vs recursive and stack-based DFS

Practice

PythonBFS vs DFS paths, and queue size vs stack depth on three graph shapes

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

No comments yet. Share how you would answer it.

Question 85 of 154 in DSA

Keep your momentum going.

Mark this question solved to track your progress, then take the next one while it is fresh.

All DSA questions

Up nextMedium→

How do you find the maximum product subarray?

Continue