Faangprep Logo
Log inStart free
Browse curriculum

Introduction to BFS

Explore data structures layer by layer using a Queue.

Easy
15 min
Solve on LeetCode

Examples

Input:root = [3,9,20,null,null,15,7]
Output:[[3],[9,20],[15,7]]
Explain:

Each inner list is one level, top to bottom, left to right.

Input:root = [1]
Output:[[1]]
Explain:

A single node is a single level.

Input:root = []
Output:[]
Explain:

An empty tree has no levels.

What is Breadth-First Search?

Breadth-First Search (BFS) is a fundamental graph and tree traversal algorithm.

Unlike DFS which dives deep, BFS explores the world layer by layer. Imagine dropping a stone in a pond; the ripples expand outwards in perfect circles. BFS is that ripple, visiting all neighbors at distance 1, then all at distance 2, and so on.

The Motivation: Shortest Path

The #1 reason to use BFS is to find the Shortest Path in an unweighted graph.

"Find the minimum number of steps to get from A to B."

Because BFS guarantees we visit nodes in order of their distance from the start, the first time we reach the target, we are guaranteed to have found the shortest path.

BFS vs DFS

Why not always use DFS?

  • DFS might go 1000 steps down the wrong path before realizing the target was just 1 step to the right.
  • BFS checks everything at distance 1 first.

Trade-off: BFS typically uses more memory (Queue stores an entire level) than DFS (Stack stores just a single path).

The Intuition: Queue (FIFO)

BFS logic utilizes a FIFO (First-In, First-Out) Queue.

  1. Enqueue the start node.
  2. Dequeue a node and Visit it.
  3. Enqueue all its unvisited neighbors.

This ensures that nodes discovered earlier (closer to start) are processed before nodes discovered later.

Interactive Walkthrough

#n = VISIT ORDER · OUTLINED = WAITING IN THE QUEUE

ENQUEUE ROOT

Queue size

1

Levels done

0

queue (front first)

3

current level

Not collecting

result

[]

 

Put the root, 3, in the queue

Next

Level 0: size = 1. The queue holds exactly this level

Tree

Legend & Complexity

The node just dequeued

Waiting in the queue — the front of the queue list is dequeued next

Dequeued; #n is the order it came out

Time

O(n)

Space

O(w) queue, w = widest level

Run level order traversal on a tree written the LeetCode way, nulls included. At the start of each level the queue holds exactly that level; each dequeued node is recorded and its children join the back of the queue. The number under a node is the order it came out of the queue — top to bottom, left to right.

Dry Run Table

Tree: [1, 2, 3, 4] — root 1, children 2 and 3, and 4 as the left child of 2.

Level Queue at start size Dequeued Enqueued result
0 [1] 1 1 2, 3 [[1]]
1 [2, 3] 2 2, then 3 4 (from 2) [[1], [2, 3]]
2 [4] 1 4 — [[1], [2, 3], [4]]

The queue is empty, so the method returns [[1], [2, 3], [4]].

When should I use BFS?

Pattern Recognition Triggers:

Use BFS immediately if you see:

  1. "Shortest Path": Minimum steps, level, or distance.
  2. "Level Order Traversal": Printing trees row by row.
  3. "Connected Components": (Can use DFS too, but BFS is common).
  4. "Minimum Knight Moves" / "Rotting Oranges": Simultaneous expansion problems.

The Solution Template

LeetCode 102, Binary Tree Level Order Traversal: the level-by-level queue template every lesson in this section builds on.

Introduction to BFS Code
1var levelOrder = function(root) {
2    const result = [];
3    if (!root) {
4        return result;
5    }
6    const queue = [root];
7    let head = 0;
8    while (head < queue.length) {
9        const size = queue.length - head;
10        const level = [];
11        for (let i = 0; i < size; i++) {
12            const node = queue[head++];
13            level.push(node.val);
14            if (node.left) {
15                queue.push(node.left);
16            }
17            if (node.right) {
18                queue.push(node.right);
19            }
20        }
21        result.push(level);
22    }
23    return result;
24};

Edge Cases & Common Mistakes

Checklist:

  • Null Root: Always check if (!root) return.
  • Cycles (Graphs): MUST use a visited set for graphs, or infinite loop occurs.
  • Queue Size: In Java/C++, use standard Queue interface. In JavaScript, shift() on an array is O(n), so the JavaScript and TypeScript code below keeps a head index into the array instead.

Common Mistakes:

  • Using a Stack (DFS) instead of a Queue.
  • Forgetting to mark nodes as visited when adding to queue (not when popping) in graphs (causes duplicates).

Summary

Recap:

  • Pattern: Queue (FIFO).
  • Concept: Layer by Layer / Ripple Effect.
  • Best For: Shortest Path, Level Order.
Next

BFS Fundamentals & Patterns

The approach, step by step

  1. Seed the queue

    Return an empty result for an empty tree; otherwise put the root in the queue.

  2. Take one level

    Read the queue’s size and dequeue that many nodes, collecting their values.

  3. Enqueue children

    For each dequeued node, enqueue its left child and then its right child, and append the level to the result.

Frequently asked questions

What is breadth-first search?

A way to visit every node in order of distance from the start: first the root, then all of its children, then all of their children. On a binary tree that is level order — top to bottom, left to right.

Why does BFS use a queue?

A queue is first in, first out. Children join the back as their parents are processed, so every node of one level leaves the queue before any node of the next level does.

How does the code know where one level ends?

It reads the queue’s size before the inner loop. At that moment the queue holds exactly the current level, so dequeuing that many nodes processes the whole level and nothing more.

Want to see the mechanism first? Step through it in the visualizer:

Breadth First Search

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description