Breadth-First Search

Use Cases

Use Case	Description	Example
Level Order Traversal of a Binary Tree	Given a binary tree, return the values of its nodes in level order (breadth-first).	For the tree: 1, with children 2 and 3, and 2's children 4 and 5, and 3's children 6 and 7. The result is [[1], [2, 3], [4, 5, 6, 7]].
Finding Maximum Value at Each Level	Find the maximum value of nodes at each level of the binary tree.	For the tree: 1, with children 2 and 3. The result is [1, 3].
Checking for Completeness of a Binary Tree	Verify if the binary tree is complete by checking if all levels are fully filled except possibly the last.	For the tree: 1, with children 2 and 3. The result is True (complete).

Code Template

Initializing

queue = deque([root]): Initializes a double-ended queue (deque) with the root node of the tree. The deque is used for efficient FIFO (first-in, first-out) operations, allowing us to easily add nodes to the end and remove nodes from the front as we traverse the tree.

While loop

while queue: This line starts a loop that continues as long as there are nodes in the queue. It ensures that we process each level of the tree until all nodes have been visited.
level_size = len(queue): This line calculates the number of nodes at the current level by getting the length of the queue. This value, level_size, will be used to determine how many nodes to process in this iteration of the loop.
level = []: This line initializes an empty list named level. It will temporarily store the values of the nodes that are processed at the current level before adding them to the main result list.

Loop over queue

for _ in range(level_size): Starts a loop that will iterate level_size times, where level_size is the number of nodes at the current level. The underscore _ is used as a variable name to indicate that the loop variable is not needed within the loop body.
node = queue.popleft(): Removes and retrieves the leftmost (or front) node from the queue. The popleft() method is specific to deques and is efficient for removing elements from the front. The variable node now holds the current node being processed.
level.append(node.val): Adds the value of the current node (accessed via node.val) to the level list. This collects the values of all nodes at the current level in the level list for later use.

Update queue

if node.left: Checks if the current node (stored in the variable node) has a left child. If the left child exists (i.e., it is not None), the following line will execute.
queue.append(node.left): If the left child exists, this line adds the left child node to the end of the queue. This ensures that the left child will be processed in subsequent iterations of the BFS loop.
result.append(level): Adds the list level, which contains the values of all nodes at the current level of the tree or graph, to the result list. The result list is designed to store the values of nodes level by level, effectively capturing the structure of the traversal.

def bfs(root):
    queue = deque([root])
    result = []

Common mistakes

Wrong Level Boundary

# Wrong: process one node per outer iteration — not level-by-level
while queue:
    node = queue.popleft()
    level = [node.val]
    result.append(level)
# Correct: dequeue exactly len(queue) nodes per round = one depth level
while queue:
    level_size = len(queue)
    level = []
    for _ in range(level_size):
        node = queue.popleft()
        level.append(node.val)
        # enqueue children...
    result.append(level)

Appending the Level at the Wrong Time

# Wrong: push level inside inner loop — one entry per node
for _ in range(level_size):
    node = queue.popleft()
    level.append(node.val)
    result.append(level)  # Should run once per depth, not once per node
# Correct:
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)  # After finishing the whole level

Graph / Grid BFS Without Visited

# Wrong: enqueue the same cell many times — blows up time / memory
queue.append((nr, nc))  # No check if already seen
# Correct: mark when enqueueing (or dequeuing) so each state is processed once
if (nr, nc) not in visited:
    visited.add((nr, nc))
    queue.append((nr, nc))
# Grids: often mutate board '#' or use a visited matrix

Issues and consideration

BFS VS DFS: BFS is ideal for scenarios where you need the shortest path or to explore nodes level by level. DFS is better suited for problems that require exploring all possible options or paths, especially when the solution is deep in the tree or graph.

102. Binary Tree Level Order Traversal

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        queue = deque([root])
        result = []
        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

103. Binary Tree Zigzag Level Order Traversal

class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        queue = deque([root])
        result = []
        left_to_right = True
        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)
            if not left_to_right:
                level.reverse()
            result.append(level)
            left_to_right = not left_to_right
        return result

199. Binary Tree Right Side View

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        queue = deque([root])
        result = []
        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[-1])
        return result

637. Average of Levels in Binary Tree

class Solution:
    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        if not root:
            return []
        queue = deque([root])
        result = []
        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(sum(level) / len(level))
        return result

Breadth-First Search

Use Cases

Code Template

Initializing

While loop

Loop over queue

Update queue

Common mistakes

Issues and consideration

Related Problem