BFS Fundamentals & Patterns
Simple BFS versus level-order BFS, and why the queue finds the shallowest answer first.
Examples
9 is a leaf at depth 2, reached before 15 and 7.
The only leaf, 6, is at depth 5.
Standard BFS vs Level-Order BFS
There are two ways to write the BFS loop, and the difference is one line.
Simple BFS dequeues one node at a time. Use it when you only need to reach every node, or find a target, and do not care which level anything is on:
queue = deque([root])
while queue:
node = queue.popleft()
# process node
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
Level-order BFS reads size = len(queue) before the inner loop. At that moment the queue holds exactly one level — every node at the current depth, and nothing deeper — so the inner loop processes one whole level, and code after it runs once per level:
queue = deque([root])
while queue:
size = len(queue)
for _ in range(size):
node = queue.popleft()
# every node here is at the same depth
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
# end of one level
Because nodes leave the queue in order of depth, the first time BFS meets something is at the smallest depth it can be met. The figure below shows that on Minimum Depth: the run stops at the first leaf it dequeues.
Interactive Visualization
dN = DEPTH THE NODE WAS ENQUEUED AT
ENQUEUE ROOT
depth
1
Min depth
—
queue (front first)
Put the root, 3, in the queue. depth = 1
Next
depth 1: the 1 node in the queue are all at depth 1
Tree
Legend & Complexity
The node just dequeued
Waiting in the queue; dN is its depth
Dequeued — or, emphasised, the first leaf, where the run stops
Time
O(n)
Space
O(w) queue, w = widest level
Level-order BFS on LeetCode 111, Minimum Depth. Each node is labeled with the depth it was enqueued at; the queue beside the tree never holds more than two neighboring depths, and the front always holds the smaller. The first leaf dequeued is at the smallest depth any leaf has, so the method returns right there.
Code: Minimum Depth (LeetCode 111)
The level-order template with one extra check: return the depth at the first node with no children.
BFS Fundamentals & Patterns Code
1var minDepth = function(root) {2 if (!root) {3 return 0;4 }5 const queue = [root];6 let head = 0;7 let depth = 1;8 while (head < queue.length) {9 const size = queue.length - head;10 for (let i = 0; i < size; i++) {11 const node = queue[head++];12 if (!node.left && !node.right) {13 return depth;14 }15 if (node.left) {16 queue.push(node.left);17 }18 if (node.right) {19 queue.push(node.right);20 }21 }22 depth++;23 }24 return depth;25};
Trees vs Graphs
Trees:
- No cycles.
- Usually directed (Parent -> Child).
- No
visitedset needed (unless traversing up to parents).
Graphs:
- Can have cycles (A -> B -> A).
- Can be undirected.
- MUST use
visitedset to prevent infinite loops.
Queue Performance
BFS dequeues once per node, so dequeue has to be O(1). Python's collections.deque, Java's ArrayDeque and C++'s std::queue all are. A JavaScript array's shift() is not — it moves every remaining element — so the JavaScript and TypeScript code keeps a head index and reads queue[head++] instead. In C, a plain array with head and tail indices does the same job.