BFS vs DFS
Two search strategies
When traversing a tree to find a solution node, two fundamental strategies exist:
| Property | Depth-First Search (DFS) | Breadth-First Search (BFS) |
|---|---|---|
| Order | Explore one subtree fully before siblings | Explore all nodes at level k before level k+1 |
| Data structure | Stack (LIFO) | Queue (FIFO) |
| Space complexity | O(d) where d is depth | O(bd) where b is branching factor |
| Completeness | Incomplete for infinite/deep trees | Complete - finds solution if one exists |
| Optimality | May find deep solution before shallow one | Finds nearest (shortest path) solution first |
Depth-first behaviour
DFS goes deep before going wide. At each node, the left subtree is explored completely before the right subtree. Preorder, inorder, and postorder traversals are all depth-first.
Problem: If the left subtree is infinite, DFS never reaches the right subtree. A solution sitting at the top of the right subtree will never be found.
Breadth-first behaviour
BFS visits nodes level by level horizontally. When visiting a node, it does not traverse its children until it has visited all other nodes at the current depth.
Implementation idea: Maintain a list of pending trees to visit. Initially contains just the root. Each step removes a tree from the front, and if it is a branch, adds its children to the back.
Problem: The space requirement grows exponentially with depth. At depth d, up to bd nodes may be stored simultaneously.
When to use each
- DFS when the tree is finite, solutions are plentiful, and memory is constrained.
- BFS when the shortest path matters, or when the tree may be infinite/unbalanced.
- Neither is ideal for large/infinite search spaces - iterative deepening (see later) combines their strengths.