Data Structures & AlgorithmsBreadth-First Search (BFS)

Breadth-First Search (BFS) — Algorithm & Applications

LevelIntermediate

Duration75 mins

TopicBreadth-First Search (BFS)

3 / 5

Level-by-Level Traversal — The Power of Layered Exploration

Thinking in Layers: BFS's Hidden Superpower

BFS naturally organizes exploration into "levels" or "layers"—vertices at distance 0 form level 0, vertices at distance 1 form level 1, and so on. While this layered structure is fundamental to BFS's shortest path guarantee, it's also a standalone feature that enables elegant solutions to many problems.

When a problem requires you to:

Process nodes depth-by-depth in a tree
Find the minimum number of transformations between two states
Identify all vertices at a specific distance
Track which "generation" or "wave" discovered each vertex
Alternate processing patterns at different depths

...you're likely looking at a level-by-level BFS problem.

This page explores how to explicitly work with BFS levels, the patterns for tracking level boundaries, and classic problems that exploit the layered structure.

What You Will Learn

By the end of this page, you'll master techniques for explicit level tracking in BFS, understand the depth-tracking pattern, and be able to recognize and solve problems that require layer-aware processing. You'll see these patterns applied to tree level-order traversal, word ladder transformations, and grid-based distance problems.

Explicit Level Tracking: Knowing Where You Are

Standard BFS computes the distance to each vertex but doesn't explicitly distinguish when one level ends and the next begins. For many applications, we need to track level boundaries—processing all vertices at one level before moving to the next.

Why level boundaries matter:

Consider these problems:

Tree level-order traversal: Return a list of lists, where each inner list contains all nodes at one level
Minimum transformations: Count the number of transformation steps (not just the final distance)
Zigzag traversal: Process left-to-right at odd levels, right-to-left at even levels
Level-specific operations: Apply different logic depending on depth

In all cases, we need to know when we've finished one level and started the next.

Pattern 1: Count-based level tracking

The simplest approach: before processing any level, count how many vertices are in the queue. That's exactly the number of vertices at the current level.

level-tracking-patterns
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
from collections import deque
from typing import List, Optional
 
class TreeNode:
    def __init__(self, val: int = 0, left: 'TreeNode' = None, right: 'TreeNode' = None):
        self.val = val
        self.left = left
        self.right = right
 
def level_order_traversal(root: Optional[TreeNode]) -> List[List[int]]:
    """
    Return level-order traversal as list of lists.
    Each inner list contains all node values at one level.
    
    Pattern: Count-based level tracking
    """
    if not root:
        return []
    
    result: List[List[int]] = []
    queue: deque = deque([root])
    
    while queue:
        # Key insight: len(queue) is exactly the number of nodes at current level
        level_size = len(queue)
        current_level: List[int] = []
        
        # Process exactly level_size nodes (the entire current level)
        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)
            
            # Children go to the back of queue (next level)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(current_level)
    
    return result
 
 
def level_order_bottom_up(root: Optional[TreeNode]) -> List[List[int]]:
    """
    Level order traversal from bottom to top.
    Simply reverse the result!
    """
    return level_order_traversal(root)[::-1]
 
 
def zigzag_level_order(root: Optional[TreeNode]) -> List[List[int]]:
    """
    Zigzag traversal: alternate direction at each level.
    Level 0: left-to-right
    Level 1: right-to-left
    Level 2: left-to-right
    ...
    """
    if not root:
        return []
    
    result: List[List[int]] = []
    queue: deque = deque([root])
    left_to_right = True
    
    while queue:
        level_size = len(queue)
        current_level: List[int] = []
        
        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        # Reverse alternating levels
        if not left_to_right:
            current_level.reverse()
        
        result.append(current_level)
        left_to_right = not left_to_right
    
    return result

Pattern 2: Sentinel-based level tracking

An alternative approach uses a special "sentinel" value (like null) to mark level boundaries:

sentinel-pattern
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
from collections import deque
from typing import List, Optional
 
def level_order_sentinel(root: Optional['TreeNode']) -> List[List[int]]:
    """
    Level-order traversal using sentinel (None) to mark level boundaries.
    
    Alternative to count-based approach. Some find it more intuitive.
    """
    if not root:
        return []
    
    result: List[List[int]] = []
    queue: deque = deque([root, None])  # None is the sentinel
    current_level: List[int] = []
    
    while queue:
        node = queue.popleft()
        
        if node is None:
            # End of current level
            result.append(current_level)
            current_level = []
            
            # If queue still has elements, add sentinel for next level
            if queue:
                queue.append(None)
        else:
            current_level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    
    return result
 
 
# Trade-off comparison:
# 
# Count-based:
#   + Cleaner code (no sentinel checks)
#   + Works with any vertex type
#   + Slightly more efficient (no sentinel in queue)
#
# Sentinel-based:
#   + Makes level boundaries explicit in queue state
#   + Natural for streaming/iterative processing
#   - Requires a sentinel value distinct from valid vertices
#   - Extra queue operations for sentinel

Recommendation

The count-based approach is generally preferred for its cleanliness and efficiency. Use it as your default pattern. The sentinel approach can be useful in specialized scenarios like streaming processing or when you need to pause/resume level-by-level iteration.

Classic Application: The Word Ladder Problem

The Word Ladder problem beautifully demonstrates level-by-level BFS on an implicit graph. It's a canonical example taught across algorithms courses and appears frequently in technical interviews.

Problem statement:

Given two words (beginWord and endWord) and a dictionary of valid words, find the shortest transformation sequence from beginWord to endWord, where:

Each transformation changes exactly one letter
Each intermediate word must be in the dictionary

Return the number of words in the shortest sequence (or 0 if no transformation is possible).

Example:

beginWord = "hit"
endWord = "cog"
wordList = ["hot", "dot", "dog", "lot", "log", "cog"]
Shortest transformation: "hit" → "hot" → "dot" → "dog" → "cog"
Answer: 5 (the length of the sequence)

Why this is a graph problem:

We can model this as a graph where:

Vertices: All words (including beginWord)
Edges: Connect words that differ by exactly one letter
Problem: Find shortest path from beginWord to endWord

Since all edges have the same "weight" (one transformation), BFS finds the shortest path!

word-ladder
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
from collections import deque, defaultdict
from typing import List, Set
 
def word_ladder(beginWord: str, endWord: str, wordList: List[str]) -> int:
    """
    Find shortest transformation sequence length.
    Returns 0 if no transformation is possible.
    """
    word_set: Set[str] = set(wordList)
    
    # Edge case: endWord must be in dictionary
    if endWord not in word_set:
        return 0
    
    # BFS setup
    queue: deque = deque([(beginWord, 1)])  # (word, sequence_length)
    visited: Set[str] = {beginWord}
    
    while queue:
        current_word, length = queue.popleft()
        
        # Try all possible one-letter transformations
        for i in range(len(current_word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                # Create transformed word
                next_word = current_word[:i] + c + current_word[i+1:]
                
                # Skip if same as current or not in dictionary
                if next_word == current_word or next_word not in word_set:
                    continue
                
                # Found the target!
                if next_word == endWord:
                    return length + 1
                
                # Add to BFS frontier
                if next_word not in visited:
                    visited.add(next_word)
                    queue.append((next_word, length + 1))
    
    return 0  # No transformation possible
 
 
def word_ladder_level_based(beginWord: str, endWord: str, wordList: List[str]) -> int:
    """
    Word ladder using explicit level-based BFS.
    This version counts levels directly rather than tracking per-word length.
    """
    word_set: Set[str] = set(wordList)
    if endWord not in word_set:
        return 0
    
    queue: deque = deque([beginWord])
    visited: Set[str] = {beginWord}
    level = 1  # Current transformation level
    
    while queue:
        level_size = len(queue)
        
        # Process all words at current level
        for _ in range(level_size):
            current = queue.popleft()
            
            # Generate all one-letter transformations
            for i in range(len(current)):
                for c in 'abcdefghijklmnopqrstuvwxyz':
                    next_word = current[:i] + c + current[i+1:]
                    
                    if next_word == current:
                        continue
                    
                    if next_word == endWord:
                        return level + 1
                    
                    if next_word in word_set and next_word not in visited:
                        visited.add(next_word)
                        queue.append(next_word)
        
        level += 1
    
    return 0
 
 
def word_ladder_optimized(beginWord: str, endWord: str, wordList: List[str]) -> int:
    """
    Optimized version using pattern-based adjacency.
    
    Instead of trying 26 letters at each position, precompute which words
    match patterns like "h*t", "*ot", "ho*".
    
    Time complexity: O(M² × N) where M = word length, N = dictionary size
    vs. O(26 × M × N) for naive approach.
    """
    if endWord not in wordList:
        return 0
    
    # Precompute pattern -> words mapping
    # "hot" matches patterns: "*ot", "h*t", "ho*"
    word_len = len(beginWord)
    pattern_to_words = defaultdict(list)
    
    for word in wordList:
        for i in range(word_len):
            pattern = word[:i] + '*' + word[i+1:]
            pattern_to_words[pattern].append(word)
    
    # BFS using patterns for neighbor lookup
    queue: deque = deque([beginWord])
    visited: Set[str] = {beginWord}
    level = 1
    
    while queue:
        level_size = len(queue)
        
        for _ in range(level_size):
            current = queue.popleft()
            
            # Find neighbors via pattern matching
            for i in range(word_len):
                pattern = current[:i] + '*' + current[i+1:]
                
                for neighbor in pattern_to_words[pattern]:
                    if neighbor == endWord:
                        return level + 1
                    
                    if neighbor not in visited:
                        visited.add(neighbor)
                        queue.append(neighbor)
        
        level += 1
    
    return 0

Complexity analysis:

Let N = number of words in dictionary, M = word length:

Approach	Time	Space
Naive (26 letters)	O(N × M × 26)	O(N × M)
Pattern-based	O(N × M²)	O(N × M²)
Bidirectional	Half the depth explored	Same space

Key insights:

Implicit vs. explicit graph: We never build the adjacency list explicitly. The graph is "implicit"—we generate neighbors on-the-fly during BFS.
Level = transformation count: Each BFS level corresponds to one transformation. The level at which we find endWord is the answer.
Early termination: We check for endWord when adding to queue (not when dequeuing). This finds the answer one step earlier.
Memory optimization: Remove words from dictionary after visiting, rather than maintaining a separate visited set. (Be careful if dictionary is immutable or reused!)

Word Ladder II: Finding All Shortest Paths

A harder variant asks for all shortest transformation sequences. This requires tracking multiple parents for each word (since multiple words might lead to the same word at the same level) and then reconstructing all paths via backtracking. The BFS structure remains the same, but the reconstruction is more complex.

Grid BFS: Multi-Source Level Propagation

Grids are one of the most common settings for BFS problems. Each cell is a vertex, and edges connect adjacent cells (usually 4-directionally for Manhattan distance, or 8-directionally for Chebyshev distance).

Classic problem: Rotting Oranges

You have a grid where:

0 = empty cell
1 = fresh orange
2 = rotten orange

Each minute, any fresh orange adjacent (4-directionally) to a rotten orange becomes rotten. Return the minimum minutes until all oranges are rotten, or -1 if impossible.

Why this is multi-source level-by-level BFS:

Sources: All initially rotten oranges (value 2)
Levels: Each BFS level = one minute of rotting
Target: All fresh oranges become rotten

This is level-by-level BFS where we need to count the levels explicitly.

rotting-oranges
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
from collections import deque
from typing import List
 
def oranges_rotting(grid: List[List[int]]) -> int:
    """
    Return minimum minutes until all oranges are rotten.
    Returns -1 if impossible.
    
    Multi-source BFS with explicit level counting.
    """
    rows, cols = len(grid), len(grid[0])
    queue: deque = deque()
    fresh_count = 0
    
    # Initialize: find all rotten oranges and count fresh ones
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c))
            elif grid[r][c] == 1:
                fresh_count += 1
    
    # Edge case: no fresh oranges
    if fresh_count == 0:
        return 0
    
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    minutes = 0
    
    while queue:
        # Process all rotten oranges at current "minute"
        level_size = len(queue)
        
        for _ in range(level_size):
            r, c = queue.popleft()
            
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                
                # Check bounds and if fresh
                if (0 <= nr < rows and 0 <= nc < cols and 
                    grid[nr][nc] == 1):
                    # Orange becomes rotten
                    grid[nr][nc] = 2
                    fresh_count -= 1
                    queue.append((nr, nc))
        
        # Increment time if we made any rotting happen
        if queue:  # Still have oranges to process in next level
            minutes += 1
    
    # Check if all fresh oranges were reached
    return minutes if fresh_count == 0 else -1
 
 
def walls_and_gates(rooms: List[List[int]]) -> None:
    """
    Fill each empty room with distance to nearest gate.
    
    -1 = wall/obstacle
    0 = gate
    INF (2^31 - 1) = empty room
    
    Classic multi-source BFS: start from all gates simultaneously.
    """
    if not rooms or not rooms[0]:
        return
    
    INF = 2147483647
    rows, cols = len(rooms), len(rooms[0])
    queue: deque = deque()
    
    # Initialize: all gates are sources
    for r in range(rows):
        for c in range(cols):
            if rooms[r][c] == 0:
                queue.append((r, c))
    
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    
    while queue:
        r, c = queue.popleft()
        
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            
            # Only update if cell is empty (INF) - not wall, not gate, not already updated
            if (0 <= nr < rows and 0 <= nc < cols and 
                rooms[nr][nc] == INF):
                rooms[nr][nc] = rooms[r][c] + 1
                queue.append((nr, nc))
 
 
def shortest_path_binary_matrix(grid: List[List[int]]) -> int:
    """
    Find shortest path from top-left to bottom-right.
    Can move in 8 directions. Only traverse cells with 0.
    
    Returns path length (number of cells), or -1 if impossible.
    
    Level-by-level BFS with 8-directional movement.
    """
    n = len(grid)
    
    # Edge cases
    if grid[0][0] == 1 or grid[n-1][n-1] == 1:
        return -1
    
    if n == 1:
        return 1
    
    # 8 directions (including diagonals)
    directions = [
        (-1, -1), (-1, 0), (-1, 1),
        (0, -1),           (0, 1),
        (1, -1),  (1, 0),  (1, 1)
    ]
    
    queue: deque = deque([(0, 0)])
    grid[0][0] = 1  # Mark as visited by setting to 1
    path_length = 1
    
    while queue:
        level_size = len(queue)
        
        for _ in range(level_size):
            r, c = queue.popleft()
            
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                
                if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
                    if nr == n - 1 and nc == n - 1:
                        return path_length + 1
                    
                    grid[nr][nc] = 1  # Mark visited
                    queue.append((nr, nc))
        
        path_length += 1
    
    return -1

Grid BFS patterns summary:

Pattern	Use Case	Implementation Detail
Single-source	Path from point A to B	Standard BFS from one cell
Multi-source	Distance to nearest X	Initialize queue with all X cells
Level-counting	Min time/steps to state	Count BFS levels explicitly
In-place marking	Reduce memory	Mark visited by modifying grid
4-directional	Manhattan adjacency	directions = [(0,1), (1,0), (0,-1), (-1,0)]
8-directional	Chebyshev adjacency	Add diagonals to directions

Grid BFS Pitfalls

Boundary checking: Always verify coordinates are in bounds before accessing grid[nr][nc]. 2. Marking before enqueueing: Mark cells as visited when adding to queue, not when processing. 3. Mutating input: In-place marking destroys original data. Copy the grid if you need to preserve it. 4. Disconnected regions: Multi-source BFS handles this automatically—unreachable cells simply never get updated.

Level-Aware Processing: Advanced Patterns

Beyond simply counting levels or collecting level-by-level results, some problems require different processing logic at different levels, or need to track level-specific state.

Pattern: Level-dependent logic

Some problems require alternating behavior at each level:

level-patterns
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
from collections import deque
from typing import List, Optional
 
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
 
def largest_value_each_level(root: Optional[TreeNode]) -> List[int]:
    """
    Find the maximum value at each level of the tree.
    
    Level-aware processing: compute aggregate per level.
    """
    if not root:
        return []
    
    result = []
    queue: deque = deque([root])
    
    while queue:
        level_size = len(queue)
        level_max = float('-inf')
        
        for _ in range(level_size):
            node = queue.popleft()
            level_max = max(level_max, node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(level_max)
    
    return result
 
 
def average_of_levels(root: Optional[TreeNode]) -> List[float]:
    """
    Compute the average value at each level.
    
    Pattern: Aggregate collection during level processing.
    """
    if not root:
        return []
    
    result = []
    queue: deque = deque([root])
    
    while queue:
        level_size = len(queue)
        level_sum = 0
        
        for _ in range(level_size):
            node = queue.popleft()
            level_sum += node.val
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(level_sum / level_size)
    
    return result
 
 
def right_side_view(root: Optional[TreeNode]) -> List[int]:
    """
    Return what you'd see looking at the tree from the right side.
    This is the rightmost node at each level.
    
    Pattern: Track last node processed at each level.
    """
    if not root:
        return []
    
    result = []
    queue: deque = deque([root])
    
    while queue:
        level_size = len(queue)
        
        for i in range(level_size):
            node = queue.popleft()
            
            # Last node in level (rightmost)
            if i == level_size - 1:
                result.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    
    return result
 
 
def connect_next_pointers(root: 'Node') -> 'Node':
    """
    Populate next pointers to point to the next node on the same level.
    Perfect binary tree: each node has left and right children until leaves.
    
    Pattern: Level traversal with inter-node manipulation.
    
    class Node:
        val: int
        left: Node
        right: Node
        next: Node  # Points to next node on same level
    """
    if not root:
        return root
    
    queue: deque = deque([root])
    
    while queue:
        level_size = len(queue)
        prev = None
        
        for i in range(level_size):
            node = queue.popleft()
            
            # Connect previous node to current
            if prev:
                prev.next = node
            prev = node
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        # Last node in level points to None (already default)
    
    return root
 
 
def cousins_in_binary_tree(root: TreeNode, x: int, y: int) -> bool:
    """
    Two nodes are cousins if they're at the same depth but have different parents.
    
    Pattern: Track both depth and parent during level traversal.
    """
    if not root:
        return False
    
    queue: deque = deque([(root, None)])  # (node, parent)
    
    while queue:
        level_size = len(queue)
        x_parent = None
        y_parent = None
        
        for _ in range(level_size):
            node, parent = queue.popleft()
            
            if node.val == x:
                x_parent = parent
            if node.val == y:
                y_parent = parent
            
            if node.left:
                queue.append((node.left, node))
            if node.right:
                queue.append((node.right, node))
        
        # Check if both found at this level with different parents
        if x_parent and y_parent:
            return x_parent != y_parent
        
        # If one found but not other, not at same level
        if x_parent or y_parent:
            return False
    
    return False

Pattern catalog for level-aware BFS:

Problem Type	Level-Aware Technique	Example
Level aggregation	Compute sum/max/min per level	Average of levels, max per level
Positional queries	Track first/last in level	Right side view, left side view
Inter-node connections	Link nodes within same level	Connect next pointers
Relative positioning	Track parent or siblings	Cousins detection
Conditional termination	Stop at specific level	Find nodes at depth k
Level-specific transformation	Different logic per level	Zigzag traversal

Summary: Mastering Level-by-Level Traversal

Level-by-level traversal transforms BFS from a shortest-path algorithm into a powerful pattern for layer-aware processing. Let's consolidate the key insights:

Key Takeaways

•Count-based level tracking is the standard pattern — Snapshot queue size at each level's start; that's exactly the node count for that level.
•Level = distance = transformation count — In Word Ladder and similar problems, BFS levels directly correspond to the answer (minimum steps).
•Grid BFS is level-by-level BFS on an implicit graph — Cells are vertices, adjacency is direction-based, and grid modifications can mark visited.
•Multi-source BFS + level counting solves spreading problems — Rotting oranges, shortest distance to any X, wavefront propagation.
•Level-aware processing enables rich patterns — Aggregation (averages), positional queries (rightmost), inter-node operations (next pointers).
•Explicit level tracking doesn't change complexity — Still O(V + E); we're just organizing the work differently.

What's next:

With mechanics, queue behavior, and level-by-level patterns mastered, the next page covers Time Complexity Analysis and BFS Applications. We'll rigorously analyze BFS's O(V + E) complexity, understand what makes it efficient, and survey the breadth of problems BFS elegantly solves.

Page Complete

You now understand how to leverage BFS's level structure for a wide range of problems. You can track level boundaries, count transformation steps, process grids, and apply level-aware patterns like aggregation and positional queries. Next, we'll analyze BFS complexity and explore its applications.

3 / 5

Loading learning content...

Data Structures & AlgorithmsBreadth-First Search (BFS)

Breadth-First Search (BFS) — Algorithm & Applications

LevelIntermediate

Duration75 mins

TopicBreadth-First Search (BFS)

3 / 5

Level-by-Level Traversal — The Power of Layered Exploration

Thinking in Layers: BFS's Hidden Superpower

When a problem requires you to:

Process nodes depth-by-depth in a tree
Find the minimum number of transformations between two states
Identify all vertices at a specific distance
Track which "generation" or "wave" discovered each vertex
Alternate processing patterns at different depths

...you're likely looking at a level-by-level BFS problem.

This page explores how to explicitly work with BFS levels, the patterns for tracking level boundaries, and classic problems that exploit the layered structure.

What You Will Learn

Explicit Level Tracking: Knowing Where You Are

Why level boundaries matter:

Consider these problems:

Tree level-order traversal: Return a list of lists, where each inner list contains all nodes at one level
Minimum transformations: Count the number of transformation steps (not just the final distance)
Zigzag traversal: Process left-to-right at odd levels, right-to-left at even levels
Level-specific operations: Apply different logic depending on depth

In all cases, we need to know when we've finished one level and started the next.

Pattern 1: Count-based level tracking

The simplest approach: before processing any level, count how many vertices are in the queue. That's exactly the number of vertices at the current level.

level-tracking-patterns
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
from collections import deque
from typing import List, Optional
 
class TreeNode:
    def __init__(self, val: int = 0, left: 'TreeNode' = None, right: 'TreeNode' = None):
        self.val = val
        self.left = left
        self.right = right
 
def level_order_traversal(root: Optional[TreeNode]) -> List[List[int]]:
    """
    Return level-order traversal as list of lists.
    Each inner list contains all node values at one level.
    
    Pattern: Count-based level tracking
    """
    if not root:
        return []
    
    result: List[List[int]] = []
    queue: deque = deque([root])
    
    while queue:
        # Key insight: len(queue) is exactly the number of nodes at current level
        level_size = len(queue)
        current_level: List[int] = []
        
        # Process exactly level_size nodes (the entire current level)
        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)
            
            # Children go to the back of queue (next level)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(current_level)
    
    return result
 
 
def level_order_bottom_up(root: Optional[TreeNode]) -> List[List[int]]:
    """
    Level order traversal from bottom to top.
    Simply reverse the result!
    """
    return level_order_traversal(root)[::-1]
 
 
def zigzag_level_order(root: Optional[TreeNode]) -> List[List[int]]:
    """
    Zigzag traversal: alternate direction at each level.
    Level 0: left-to-right
    Level 1: right-to-left
    Level 2: left-to-right
    ...
    """
    if not root:
        return []
    
    result: List[List[int]] = []
    queue: deque = deque([root])
    left_to_right = True
    
    while queue:
        level_size = len(queue)
        current_level: List[int] = []
        
        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        # Reverse alternating levels
        if not left_to_right:
            current_level.reverse()
        
        result.append(current_level)
        left_to_right = not left_to_right
    
    return result

Pattern 2: Sentinel-based level tracking

An alternative approach uses a special "sentinel" value (like null) to mark level boundaries:

sentinel-pattern
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
from collections import deque
from typing import List, Optional
 
def level_order_sentinel(root: Optional['TreeNode']) -> List[List[int]]:
    """
    Level-order traversal using sentinel (None) to mark level boundaries.
    
    Alternative to count-based approach. Some find it more intuitive.
    """
    if not root:
        return []
    
    result: List[List[int]] = []
    queue: deque = deque([root, None])  # None is the sentinel
    current_level: List[int] = []
    
    while queue:
        node = queue.popleft()
        
        if node is None:
            # End of current level
            result.append(current_level)
            current_level = []
            
            # If queue still has elements, add sentinel for next level
            if queue:
                queue.append(None)
        else:
            current_level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    
    return result
 
 
# Trade-off comparison:
# 
# Count-based:
#   + Cleaner code (no sentinel checks)
#   + Works with any vertex type
#   + Slightly more efficient (no sentinel in queue)
#
# Sentinel-based:
#   + Makes level boundaries explicit in queue state
#   + Natural for streaming/iterative processing
#   - Requires a sentinel value distinct from valid vertices
#   - Extra queue operations for sentinel

Recommendation

Classic Application: The Word Ladder Problem

The Word Ladder problem beautifully demonstrates level-by-level BFS on an implicit graph. It's a canonical example taught across algorithms courses and appears frequently in technical interviews.

Problem statement:

Given two words (beginWord and endWord) and a dictionary of valid words, find the shortest transformation sequence from beginWord to endWord, where:

Each transformation changes exactly one letter
Each intermediate word must be in the dictionary

Return the number of words in the shortest sequence (or 0 if no transformation is possible).

Example:

beginWord = "hit"
endWord = "cog"
wordList = ["hot", "dot", "dog", "lot", "log", "cog"]
Shortest transformation: "hit" → "hot" → "dot" → "dog" → "cog"
Answer: 5 (the length of the sequence)

Why this is a graph problem:

We can model this as a graph where:

Vertices: All words (including beginWord)
Edges: Connect words that differ by exactly one letter
Problem: Find shortest path from beginWord to endWord

Since all edges have the same "weight" (one transformation), BFS finds the shortest path!

word-ladder
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
from collections import deque, defaultdict
from typing import List, Set
 
def word_ladder(beginWord: str, endWord: str, wordList: List[str]) -> int:
    """
    Find shortest transformation sequence length.
    Returns 0 if no transformation is possible.
    """
    word_set: Set[str] = set(wordList)
    
    # Edge case: endWord must be in dictionary
    if endWord not in word_set:
        return 0
    
    # BFS setup
    queue: deque = deque([(beginWord, 1)])  # (word, sequence_length)
    visited: Set[str] = {beginWord}
    
    while queue:
        current_word, length = queue.popleft()
        
        # Try all possible one-letter transformations
        for i in range(len(current_word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                # Create transformed word
                next_word = current_word[:i] + c + current_word[i+1:]
                
                # Skip if same as current or not in dictionary
                if next_word == current_word or next_word not in word_set:
                    continue
                
                # Found the target!
                if next_word == endWord:
                    return length + 1
                
                # Add to BFS frontier
                if next_word not in visited:
                    visited.add(next_word)
                    queue.append((next_word, length + 1))
    
    return 0  # No transformation possible
 
 
def word_ladder_level_based(beginWord: str, endWord: str, wordList: List[str]) -> int:
    """
    Word ladder using explicit level-based BFS.
    This version counts levels directly rather than tracking per-word length.
    """
    word_set: Set[str] = set(wordList)
    if endWord not in word_set:
        return 0
    
    queue: deque = deque([beginWord])
    visited: Set[str] = {beginWord}
    level = 1  # Current transformation level
    
    while queue:
        level_size = len(queue)
        
        # Process all words at current level
        for _ in range(level_size):
            current = queue.popleft()
            
            # Generate all one-letter transformations
            for i in range(len(current)):
                for c in 'abcdefghijklmnopqrstuvwxyz':
                    next_word = current[:i] + c + current[i+1:]
                    
                    if next_word == current:
                        continue
                    
                    if next_word == endWord:
                        return level + 1
                    
                    if next_word in word_set and next_word not in visited:
                        visited.add(next_word)
                        queue.append(next_word)
        
        level += 1
    
    return 0
 
 
def word_ladder_optimized(beginWord: str, endWord: str, wordList: List[str]) -> int:
    """
    Optimized version using pattern-based adjacency.
    
    Instead of trying 26 letters at each position, precompute which words
    match patterns like "h*t", "*ot", "ho*".
    
    Time complexity: O(M² × N) where M = word length, N = dictionary size
    vs. O(26 × M × N) for naive approach.
    """
    if endWord not in wordList:
        return 0
    
    # Precompute pattern -> words mapping
    # "hot" matches patterns: "*ot", "h*t", "ho*"
    word_len = len(beginWord)
    pattern_to_words = defaultdict(list)
    
    for word in wordList:
        for i in range(word_len):
            pattern = word[:i] + '*' + word[i+1:]
            pattern_to_words[pattern].append(word)
    
    # BFS using patterns for neighbor lookup
    queue: deque = deque([beginWord])
    visited: Set[str] = {beginWord}
    level = 1
    
    while queue:
        level_size = len(queue)
        
        for _ in range(level_size):
            current = queue.popleft()
            
            # Find neighbors via pattern matching
            for i in range(word_len):
                pattern = current[:i] + '*' + current[i+1:]
                
                for neighbor in pattern_to_words[pattern]:
                    if neighbor == endWord:
                        return level + 1
                    
                    if neighbor not in visited:
                        visited.add(neighbor)
                        queue.append(neighbor)
        
        level += 1
    
    return 0

Complexity analysis:

Let N = number of words in dictionary, M = word length:

Approach	Time	Space
Naive (26 letters)	O(N × M × 26)	O(N × M)
Pattern-based	O(N × M²)	O(N × M²)
Bidirectional	Half the depth explored	Same space

Key insights:

Implicit vs. explicit graph: We never build the adjacency list explicitly. The graph is "implicit"—we generate neighbors on-the-fly during BFS.
Level = transformation count: Each BFS level corresponds to one transformation. The level at which we find endWord is the answer.
Early termination: We check for endWord when adding to queue (not when dequeuing). This finds the answer one step earlier.
Memory optimization: Remove words from dictionary after visiting, rather than maintaining a separate visited set. (Be careful if dictionary is immutable or reused!)

Word Ladder II: Finding All Shortest Paths

Grid BFS: Multi-Source Level Propagation

Classic problem: Rotting Oranges

You have a grid where:

0 = empty cell
1 = fresh orange
2 = rotten orange

Each minute, any fresh orange adjacent (4-directionally) to a rotten orange becomes rotten. Return the minimum minutes until all oranges are rotten, or -1 if impossible.

Why this is multi-source level-by-level BFS:

Sources: All initially rotten oranges (value 2)
Levels: Each BFS level = one minute of rotting
Target: All fresh oranges become rotten

This is level-by-level BFS where we need to count the levels explicitly.

rotting-oranges
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
from collections import deque
from typing import List
 
def oranges_rotting(grid: List[List[int]]) -> int:
    """
    Return minimum minutes until all oranges are rotten.
    Returns -1 if impossible.
    
    Multi-source BFS with explicit level counting.
    """
    rows, cols = len(grid), len(grid[0])
    queue: deque = deque()
    fresh_count = 0
    
    # Initialize: find all rotten oranges and count fresh ones
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c))
            elif grid[r][c] == 1:
                fresh_count += 1
    
    # Edge case: no fresh oranges
    if fresh_count == 0:
        return 0
    
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    minutes = 0
    
    while queue:
        # Process all rotten oranges at current "minute"
        level_size = len(queue)
        
        for _ in range(level_size):
            r, c = queue.popleft()
            
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                
                # Check bounds and if fresh
                if (0 <= nr < rows and 0 <= nc < cols and 
                    grid[nr][nc] == 1):
                    # Orange becomes rotten
                    grid[nr][nc] = 2
                    fresh_count -= 1
                    queue.append((nr, nc))
        
        # Increment time if we made any rotting happen
        if queue:  # Still have oranges to process in next level
            minutes += 1
    
    # Check if all fresh oranges were reached
    return minutes if fresh_count == 0 else -1
 
 
def walls_and_gates(rooms: List[List[int]]) -> None:
    """
    Fill each empty room with distance to nearest gate.
    
    -1 = wall/obstacle
    0 = gate
    INF (2^31 - 1) = empty room
    
    Classic multi-source BFS: start from all gates simultaneously.
    """
    if not rooms or not rooms[0]:
        return
    
    INF = 2147483647
    rows, cols = len(rooms), len(rooms[0])
    queue: deque = deque()
    
    # Initialize: all gates are sources
    for r in range(rows):
        for c in range(cols):
            if rooms[r][c] == 0:
                queue.append((r, c))
    
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    
    while queue:
        r, c = queue.popleft()
        
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            
            # Only update if cell is empty (INF) - not wall, not gate, not already updated
            if (0 <= nr < rows and 0 <= nc < cols and 
                rooms[nr][nc] == INF):
                rooms[nr][nc] = rooms[r][c] + 1
                queue.append((nr, nc))
 
 
def shortest_path_binary_matrix(grid: List[List[int]]) -> int:
    """
    Find shortest path from top-left to bottom-right.
    Can move in 8 directions. Only traverse cells with 0.
    
    Returns path length (number of cells), or -1 if impossible.
    
    Level-by-level BFS with 8-directional movement.
    """
    n = len(grid)
    
    # Edge cases
    if grid[0][0] == 1 or grid[n-1][n-1] == 1:
        return -1
    
    if n == 1:
        return 1
    
    # 8 directions (including diagonals)
    directions = [
        (-1, -1), (-1, 0), (-1, 1),
        (0, -1),           (0, 1),
        (1, -1),  (1, 0),  (1, 1)
    ]
    
    queue: deque = deque([(0, 0)])
    grid[0][0] = 1  # Mark as visited by setting to 1
    path_length = 1
    
    while queue:
        level_size = len(queue)
        
        for _ in range(level_size):
            r, c = queue.popleft()
            
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                
                if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
                    if nr == n - 1 and nc == n - 1:
                        return path_length + 1
                    
                    grid[nr][nc] = 1  # Mark visited
                    queue.append((nr, nc))
        
        path_length += 1
    
    return -1

Grid BFS patterns summary:

Pattern	Use Case	Implementation Detail
Single-source	Path from point A to B	Standard BFS from one cell
Multi-source	Distance to nearest X	Initialize queue with all X cells
Level-counting	Min time/steps to state	Count BFS levels explicitly
In-place marking	Reduce memory	Mark visited by modifying grid
4-directional	Manhattan adjacency	directions = [(0,1), (1,0), (0,-1), (-1,0)]
8-directional	Chebyshev adjacency	Add diagonals to directions

Grid BFS Pitfalls

Boundary checking: Always verify coordinates are in bounds before accessing grid[nr][nc]. 2. Marking before enqueueing: Mark cells as visited when adding to queue, not when processing. 3. Mutating input: In-place marking destroys original data. Copy the grid if you need to preserve it. 4. Disconnected regions: Multi-source BFS handles this automatically—unreachable cells simply never get updated.

Level-Aware Processing: Advanced Patterns

Beyond simply counting levels or collecting level-by-level results, some problems require different processing logic at different levels, or need to track level-specific state.

Pattern: Level-dependent logic

Some problems require alternating behavior at each level:

level-patterns
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
from collections import deque
from typing import List, Optional
 
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
 
def largest_value_each_level(root: Optional[TreeNode]) -> List[int]:
    """
    Find the maximum value at each level of the tree.
    
    Level-aware processing: compute aggregate per level.
    """
    if not root:
        return []
    
    result = []
    queue: deque = deque([root])
    
    while queue:
        level_size = len(queue)
        level_max = float('-inf')
        
        for _ in range(level_size):
            node = queue.popleft()
            level_max = max(level_max, node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(level_max)
    
    return result
 
 
def average_of_levels(root: Optional[TreeNode]) -> List[float]:
    """
    Compute the average value at each level.
    
    Pattern: Aggregate collection during level processing.
    """
    if not root:
        return []
    
    result = []
    queue: deque = deque([root])
    
    while queue:
        level_size = len(queue)
        level_sum = 0
        
        for _ in range(level_size):
            node = queue.popleft()
            level_sum += node.val
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(level_sum / level_size)
    
    return result
 
 
def right_side_view(root: Optional[TreeNode]) -> List[int]:
    """
    Return what you'd see looking at the tree from the right side.
    This is the rightmost node at each level.
    
    Pattern: Track last node processed at each level.
    """
    if not root:
        return []
    
    result = []
    queue: deque = deque([root])
    
    while queue:
        level_size = len(queue)
        
        for i in range(level_size):
            node = queue.popleft()
            
            # Last node in level (rightmost)
            if i == level_size - 1:
                result.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    
    return result
 
 
def connect_next_pointers(root: 'Node') -> 'Node':
    """
    Populate next pointers to point to the next node on the same level.
    Perfect binary tree: each node has left and right children until leaves.
    
    Pattern: Level traversal with inter-node manipulation.
    
    class Node:
        val: int
        left: Node
        right: Node
        next: Node  # Points to next node on same level
    """
    if not root:
        return root
    
    queue: deque = deque([root])
    
    while queue:
        level_size = len(queue)
        prev = None
        
        for i in range(level_size):
            node = queue.popleft()
            
            # Connect previous node to current
            if prev:
                prev.next = node
            prev = node
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        # Last node in level points to None (already default)
    
    return root
 
 
def cousins_in_binary_tree(root: TreeNode, x: int, y: int) -> bool:
    """
    Two nodes are cousins if they're at the same depth but have different parents.
    
    Pattern: Track both depth and parent during level traversal.
    """
    if not root:
        return False
    
    queue: deque = deque([(root, None)])  # (node, parent)
    
    while queue:
        level_size = len(queue)
        x_parent = None
        y_parent = None
        
        for _ in range(level_size):
            node, parent = queue.popleft()
            
            if node.val == x:
                x_parent = parent
            if node.val == y:
                y_parent = parent
            
            if node.left:
                queue.append((node.left, node))
            if node.right:
                queue.append((node.right, node))
        
        # Check if both found at this level with different parents
        if x_parent and y_parent:
            return x_parent != y_parent
        
        # If one found but not other, not at same level
        if x_parent or y_parent:
            return False
    
    return False

Pattern catalog for level-aware BFS:

Problem Type	Level-Aware Technique	Example
Level aggregation	Compute sum/max/min per level	Average of levels, max per level
Positional queries	Track first/last in level	Right side view, left side view
Inter-node connections	Link nodes within same level	Connect next pointers
Relative positioning	Track parent or siblings	Cousins detection
Conditional termination	Stop at specific level	Find nodes at depth k
Level-specific transformation	Different logic per level	Zigzag traversal

Summary: Mastering Level-by-Level Traversal

Level-by-level traversal transforms BFS from a shortest-path algorithm into a powerful pattern for layer-aware processing. Let's consolidate the key insights:

Key Takeaways

•Count-based level tracking is the standard pattern — Snapshot queue size at each level's start; that's exactly the node count for that level.
•Level = distance = transformation count — In Word Ladder and similar problems, BFS levels directly correspond to the answer (minimum steps).
•Grid BFS is level-by-level BFS on an implicit graph — Cells are vertices, adjacency is direction-based, and grid modifications can mark visited.
•Multi-source BFS + level counting solves spreading problems — Rotting oranges, shortest distance to any X, wavefront propagation.
•Level-aware processing enables rich patterns — Aggregation (averages), positional queries (rightmost), inter-node operations (next pointers).
•Explicit level tracking doesn't change complexity — Still O(V + E); we're just organizing the work differently.

What's next:

Page Complete

3 / 5