Same tree, two ordersCore idea
BFS: breadth-first searchHow it works
BFS explores every neighbour at the current distance before moving further out. It uses a queue, and in an unweighted graph the first time it reaches a node is along a shortest path.
function bfs(graph: Map<number, number[]>, start: number): number[] {
const visited = new Set<number>();
const queue = [start];
const result: number[] = [];
visited.add(start);
while (queue.length) {
const node = queue.shift()!;
result.push(node);
for (const neighbor of graph.get(node) || []) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor);
}
}
}
return result;
}DFS: depth-first searchHow it works
DFS follows one path as far as it can, then backs up and tries the next. It uses a stack (usually the call stack, through recursion), and on wide graphs it uses less memory than BFS.
function dfs(graph: Map<number, number[]>, start: number): number[] {
const visited = new Set<number>();
const result: number[] = [];
function explore(node: number) {
visited.add(node);
result.push(node);
for (const neighbor of graph.get(node) || []) {
if (!visited.has(neighbor)) explore(neighbor);
}
}
explore(start);
return result;
}When to use whichCompare
| Scenario | Use | Why |
|---|---|---|
| Shortest path (unweighted) | BFS | It goes level by level, so the first time you reach the target is the shortest path. |
| Does a path exist? | Either | Both can tell whether two nodes are connected. |
| Visit every node | Either | Both visit everything. |
| Topological sort | DFS | The post-order of a DFS gives a valid order naturally. |
| Detect a cycle | DFS | DFS spots a back edge using the current recursion path. |
| Level-order traversal | BFS | BFS processes a tree one level at a time. |
| Tight on memory | DFS | DFS uses O(height) space; BFS uses O(width). |
Common mistakesPitfalls
In the interviewIn the interview
Frequently asked questionsFAQ
When should you use BFS instead of DFS?
Use BFS when you need the shortest path in terms of edge count on a uniform-weight graph, or level-by-level processing such as printing a tree by rows. BFS visits nodes in order of distance from the source, so the first time you reach a target guarantees the minimum number of edges.
Why is DFS preferred for cycle detection in directed graphs?
DFS keeps a stack of the current recursion path, so it can detect a back edge pointing to an ancestor, which signals a cycle in a directed graph. Kahn's algorithm using BFS and in-degree counts also works. DFS is simpler when the graph is already traversal-oriented.
What is the time complexity of BFS and DFS?
Both visit every vertex and edge once in the worst case, giving O(V + E) time with an adjacency list and O(V^2) with an adjacency matrix. Space is O(V) for the visited set plus the queue for BFS or the recursion stack for DFS.
Now explain bfs vs dfs to me out loud
I'll give you interview problems and ask follow-ups, like a real interviewer.