sko.kr

Breadth-First Search (BFS)

algorithmsgraph-traversaltree-traversalbfsqueueshortest-path
By sko•10/7/2025•5 min read

When to use Breadth-First Search

Use BFS when you need to explore nodes layer by layer or find the shortest path in unweighted graphs. While most commonly used for level-order traversal, it can be adapted for:

  • Level-order tree traversal (classic use case)
  • Shortest path in unweighted graphs (guaranteed optimal due to layer-by-layer exploration)
  • Finding all nodes at distance k from a starting point
  • Checking if graph is bipartite (can split nodes into two groups where no two nodes in same group are connected - done by coloring nodes in alternating layers)
  • Web crawling (explore links at same depth before going deeper)
  • Social network analysis (find connections within n degrees of separation)
  • Any problem where you need to explore all possibilities at the current "distance" before moving further

Example problem

Company Org Chart: Given a company hierarchy represented as a tree, print all employees level by level to understand the reporting structure.

        CEO
       /   \
     CTO   CFO
    /  \     \
  Dev1 Dev2  Acc1

Level 0: CEO
Level 1: CTO, CFO
Level 2: Dev1, Dev2, Acc1

This shows the management layers clearly - all direct reports to the CEO first, then all their direct reports, and so on.

Single most important insight

BFS explores all nodes at distance d before any node at distance d+1 - and by using a queue (FIFO), we guarantee that nodes are processed in the exact order they were discovered, which automatically gives us level-by-level exploration and shortest paths in unweighted graphs.

Mental note: The algorithm's genius lies in the queue's FIFO property. When you discover a node's neighbors, they go to the back of the queue. This means all nodes at the current level get processed before any node at the next level. It's like filling a theater row by row - you can't start row 3 until row 2 is completely full.

Decision Framework

At every node, you face one simple decision:

  • Process the current node (mark as visited)
  • Add all unvisited neighbors to the queue for future exploration

The queue enforces the order - you don't decide when to process nodes, the FIFO structure does that for you.

Code

class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function bfs(root) {
  // Handle empty tree
  if (root == null) {
    return;
  }

  // Initialize queue with root node
  const queue = [root];
  let level = 0;

  // Process nodes level by level
  while (queue.length > 0) {
    // Capture current level size - this is key!
    const levelSize = queue.length;
    const currentLevelNodes = [];

    // Process all nodes at current level
    for (let i = 0; i < levelSize; i++) {
      // DECISION FRAMEWORK: Process current node
      const currentNode = queue.shift();
      currentLevelNodes.push(currentNode.val);

      // DECISION FRAMEWORK: Add unvisited neighbors (children) to queue
      if (currentNode.left != null) {
        queue.push(currentNode.left);
      }
      if (currentNode.right != null) {
        queue.push(currentNode.right);
      }
    }

    // Output current level
    console.log(`Level ${level}: ${currentLevelNodes.join(", ")}`);
    level++;
  }
}

// Example usage with company org chart
const ceo = new TreeNode("CEO");
const cto = new TreeNode("CTO");
const cfo = new TreeNode("CFO");
const dev1 = new TreeNode("Dev1");
const dev2 = new TreeNode("Dev2");
const acc1 = new TreeNode("Acc1");

ceo.left = cto;
ceo.right = cfo;
cto.left = dev1;
cto.right = dev2;
cfo.right = acc1;

bfs(ceo);
// Output:
// Level 0: CEO
// Level 1: CTO, CFO
// Level 2: Dev1, Dev2, Acc1

Doubt buster

Common doubt: "Why can't I just use DFS (Depth-First Search) to traverse the tree? Won't I eventually visit all nodes anyway? What makes BFS special for level-order traversal?"

This is a natural question because both BFS and DFS visit all nodes. Let's see why BFS is essential for certain problems.

Why you might think DFS could work

Consider our company org chart. With DFS, you might think:

  • "I'll go deep first: CEO → CTO → Dev1, then backtrack"
  • "Eventually I'll visit all nodes, so what's the difference?"
  • "Can't I just track depths and group nodes by their level?"

Why this thinking misses the key point

Key realization: BFS doesn't just visit all nodes - it visits them in a specific order that gives unique guarantees!

Let's compare BFS vs DFS traversal order:

BFS Order: CEO → CTO → CFO → Dev1 → Dev2 → Acc1
(All at level 0, then all at level 1, then all at level 2)

DFS Order: CEO → CTO → Dev1 → Dev2 → CFO → Acc1
(Goes deep first, jumps between levels)

Concrete example: Finding shortest path

Imagine finding the shortest path from CEO to Acc1 in an unweighted graph:

With BFS:

Step 1: Process CEO (distance 0)
Step 2: Process CTO, CFO (distance 1) - Found CFO!
Step 3: Process CFO's children - Found Acc1 at distance 2!

With DFS (might take longer path):

Step 1: Process CEO
Step 2: Process CTO (went left)
Step 3: Process Dev1 (went deeper left)
Step 4: Backtrack to CTO
Step 5: Process Dev2
Step 6: Backtrack all the way to CEO
Step 7: Finally process CFO
Step 8: Process Acc1

DFS might find a node, but won't guarantee it's via the shortest path!

Why the queue is essential

The queue in BFS acts like a "generation tracker":

  1. Generation 0 (root): Only CEO in queue
  2. Generation 1 (children): CTO and CFO added to queue
  3. Generation 2 (grandchildren): Dev1, Dev2, Acc1 added to queue

The FIFO property ensures that:

  • All Generation 1 nodes are processed before ANY Generation 2 node
  • This is impossible with DFS's stack (LIFO) or recursive call stack

The level-size trick

The critical line in BFS that enables level-by-level processing:

const levelSize = queue.length; // Snapshot of current level's size

This captures exactly how many nodes are at the current level. Even though we're adding new nodes to the queue while processing, we know exactly when one level ends and the next begins.

Why this guarantees correctness:

  • When we start processing a level, the queue contains ONLY nodes from that level
  • As we process each node, we add its children (next level) to the queue
  • But we only process levelSize nodes, so we stop exactly when the current level is complete
  • The queue now contains ONLY nodes from the next level

This elegant mechanism is why BFS can guarantee level-order traversal and shortest paths, something DFS fundamentally cannot provide due to its depth-first nature.

← Back to Blog