Breadth-First Search (BFS) Pattern

Breadth-First Search (BFS) explores nodes level by level in a tree or graph. It uses a queue to process nodes and is ideal for finding shortest paths in unweighted graphs.

When to Use This Pattern

  • Finding shortest paths in unweighted graphs
  • Level-order traversal in trees
  • Finding minimum steps to reach a target
  • Problems requiring level-by-level processing

Key Concepts

BFS uses a queue (FIFO) to process nodes level by level. It guarantees finding the shortest path in unweighted graphs.

Algorithm Section

BFS Template

from collections import deque

def bfs(start):
    queue = deque([start])
    visited = {start}
    
    while queue:
        node = queue.popleft()
        # Process node
        
        for neighbor in node.neighbors:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

Practice Problems

Problem 1: Binary Tree Level Order Traversal (LeetCode #102)

Given the root of a binary tree, return the level order traversal of its nodes' values.

Solution:

from collections import deque

def levelOrder(root):
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)
        level = []
        
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(level)
    
    return result

Explanation: We use BFS with level tracking. We process all nodes at current level before moving to next. We track level_size to know how many nodes are in current level.

Time Complexity: O(n)

Space Complexity: O(n)

Problem 2: Rotting Oranges (LeetCode #994)

You are given an m x n grid where each cell can have one of three values. Return the minimum number of minutes until no cell has a fresh orange.

Solution:

from collections import deque

def orangesRotting(grid):
    m, n = len(grid), len(grid[0])
    queue = deque()
    fresh = 0
    
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 2:
                queue.append((i, j, 0))
            elif grid[i][j] == 1:
                fresh += 1
    
    if fresh == 0:
        return 0
    
    directions = [(0,1), (1,0), (0,-1), (-1,0)]
    minutes = 0
    
    while queue:
        i, j, time = queue.popleft()
        minutes = time
        
        for di, dj in directions:
            ni, nj = i + di, j + dj
            if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 1:
                grid[ni][nj] = 2
                fresh -= 1
                queue.append((ni, nj, time + 1))
    
    return minutes if fresh == 0 else -1

Explanation: We use BFS starting from all rotten oranges. Each minute, we rot adjacent fresh oranges. We track time for each cell. If all fresh oranges are rotted, return minutes; otherwise -1.

Time Complexity: O(m × n)

Space Complexity: O(m × n)

Problem 3: Word Ladder (LeetCode #127)

A transformation sequence from word beginWord to word endWord is a sequence of words such that only one letter can be changed at a time. Return the length of the shortest transformation sequence.

Solution:

from collections import deque

def ladderLength(beginWord, endWord, wordList):
    wordSet = set(wordList)
    if endWord not in wordSet:
        return 0
    
    queue = deque([(beginWord, 1)])
    visited = {beginWord}
    
    while queue:
        word, length = queue.popleft()
        
        if word == endWord:
            return length
        
        for i in range(len(word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                newWord = word[:i] + c + word[i+1:]
                if newWord in wordSet and newWord not in visited:
                    visited.add(newWord)
                    queue.append((newWord, length + 1))
    
    return 0

Explanation: We use BFS to find shortest path. For each word, we try changing each character to all 26 letters. If the new word is in wordList and not visited, we add it to queue. BFS guarantees shortest path.

Time Complexity: O(M × N × 26) where M is word length, N is wordList size

Space Complexity: O(N)

Problem 4: Perfect Squares (LeetCode #279)

Given an integer n, return the least number of perfect square numbers that sum to n.

Solution:

from collections import deque

def numSquares(n):
    queue = deque([(n, 0)])
    visited = {n}
    
    while queue:
        num, steps = queue.popleft()
        
        if num == 0:
            return steps
        
        i = 1
        while i * i <= num:
            next_num = num - i * i
            if next_num not in visited:
                visited.add(next_num)
                queue.append((next_num, steps + 1))
            i += 1
    
    return n

Explanation: We use BFS to find minimum steps. Each level represents using one more perfect square. We subtract all possible perfect squares and add to queue. When we reach 0, we found the answer.

Time Complexity: O(n × √n)

Space Complexity: O(n)

Problem 5: Shortest Path in Binary Matrix (LeetCode #1091)

Given an n x n binary matrix grid, return the length of the shortest clear path from top-left to bottom-right.

Solution:

from collections import deque

def shortestPathBinaryMatrix(grid):
    n = len(grid)
    if grid[0][0] == 1 or grid[n-1][n-1] == 1:
        return -1
    
    queue = deque([(0, 0, 1)])
    grid[0][0] = 1  # Mark as visited
    
    directions = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]
    
    while queue:
        i, j, length = queue.popleft()
        
        if i == n-1 and j == n-1:
            return length
        
        for di, dj in directions:
            ni, nj = i + di, j + dj
            if 0 <= ni < n and 0 <= nj < n and grid[ni][nj] == 0:
                grid[ni][nj] = 1
                queue.append((ni, nj, length + 1))
    
    return -1

Explanation: We use BFS to find shortest path. We can move in 8 directions. We mark visited cells as 1. When we reach bottom-right, return length. BFS guarantees shortest path in unweighted graph.

Time Complexity: O(n²)

Space Complexity: O(n²)