BFS Level-Order Traversal

Binary Tree Level Order Traversal

Given the root of a binary tree, return the values of its nodes grouped by level, from top to bottom, with each level read left to right. For a tree like this:

3 / \ 9 20 / \ 15 7

the expected output is [[3], [9, 20], [15, 7]].

This is LeetCode 102 (Binary Tree Level Order Traversal), and it is the most natural introduction to BFS on trees. The core challenge is not just visiting nodes in breadth-first order (a standard queue handles that) but separating the output by level. BFS visits nodes level by level inherently, but a plain queue does not tell you where one level ends and the next begins.

The Level-Size Snapshot Technique

The key insight is to snapshot the queue size at the start of each level. When you begin processing a new level, the queue contains exactly the nodes at that level and nothing else. By recording that count and processing exactly that many nodes, you drain the current level while enqueuing the next level's children. When you have processed all the nodes from the snapshot, the queue now contains only the next level.

Here is how it plays out on the tree above:

Start: queue = [3]. Snapshot size = 1. Process 1 node: pop 3, add its children 9 and 20. Level result: [3].

Queue = [9, 20]. Snapshot size = 2. Process 2 nodes: pop 9 (no children), pop 20 (children 15 and 7). Level result: [9, 20].

Queue = [15, 7]. Snapshot size = 2. Process 2 nodes: pop 15, pop 7 (both are leaves). Level result: [15, 7].

Queue is empty. Done. Final result: [[3], [9, 20], [15, 7]].

The snapshot is what makes this work. Without it, you would need some other mechanism to track level boundaries, like inserting sentinel values or using two alternating queues. The snapshot approach is simpler and uses just one queue.

Code for Level Order Traversal

from collections import deque

def level_order(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

The outer while loop runs once per level. The inner for loop runs exactly level_size times, processing every node at the current level. Children enqueued during this inner loop are not processed until the next iteration of the outer loop, because the for loop's bound was fixed at the start.

Zigzag Level Order Traversal

LeetCode 103 asks for a variation where the reading direction alternates each level: left-to-right for level 0, right-to-left for level 1, left-to-right for level 2, and so on.

The BFS structure is identical. The only change is that on odd-numbered levels, you reverse the collected values before appending them to the result. Some implementations insert at the front of the level list instead of appending, or use a deque for the level list to alternate between appending left and right. But the simplest approach is to collect values normally and reverse every other level.

def zigzag_level_order(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    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

The reversal is an $O(k)$ operation where k is the level width, and across all levels it sums to $O(n)$, so it does not change the overall time complexity.

Right Side View

Consider LeetCode 199: given a binary tree, imagine yourself standing on the right side of it. Return the values of the nodes you can see, ordered from top to bottom. In other words, return the rightmost node at each level.

With the level-size snapshot pattern, this is trivial. Process each level exactly as before, and the last node you pop from the queue in each level is the rightmost one.

def right_side_view(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level_size = len(queue)
        for i in range(level_size):
            node = queue.popleft()
            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

You do not need to collect the entire level. Just check whether the current node is the last one in the level (when the loop index equals level_size - 1), and if so, record its value.

Populating Next Right Pointers

LeetCode 116 and 117 ask you to connect each node to its next right node at the same level. Each node has an additional next pointer, initially set to null. After processing, every node's next should point to the node to its right on the same level, or remain null if it is the rightmost node on that level.

The level-order BFS pattern fits perfectly. Within each level, process nodes left to right and link each node's next pointer to the node that comes after it.

def connect(root):
    if not root:
        return root
    queue = deque([root])
    while queue:
        level_size = len(queue)
        for i in range(level_size):
            node = queue.popleft()
            if i < level_size - 1:
                node.next = queue[0]
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return root

The trick here is that after popping a node, the front of the queue (queue[0]) is the next node at the same level, because all nodes at the current level were enqueued before any children. We only set the next pointer when the node is not the last in its level.

For a perfect binary tree (LeetCode 116), there is also an $O(1)$ space solution that uses the next pointers you have already set to traverse the current level and link the next level, eliminating the queue entirely. But the BFS approach works for any tree shape and is the natural starting point.

Maximum Width of Binary Tree

LeetCode 662 asks for the maximum width of a binary tree, where width is defined as the number of positions between the leftmost and rightmost non-null nodes at a level (including any null positions in between).

The standard level-order BFS does not directly give you width because width depends on node positions, not just the count of nodes. The key idea is to assign position indices. If a node is at position i, its left child is at position 2i and its right child is at 2i + 1. This mirrors the array representation of a binary tree.

def width_of_binary_tree(root):
    if not root:
        return 0
    max_width = 0
    queue = deque([(root, 0)])
    while queue:
        level_size = len(queue)
        _, first_pos = queue[0]
        for _ in range(level_size):
            node, pos = queue.popleft()
            if node.left:
                queue.append((node.left, 2 * pos))
            if node.right:
                queue.append((node.right, 2 * pos + 1))
        max_width = max(max_width, pos - first_pos + 1)
    return max_width

We store each node along with its position index. At each level, the width is last_position - first_position + 1. The variable pos after the inner loop holds the position of the last node processed at that level, and first_pos was captured at the start.

One subtlety: for very deep skewed trees, position indices can grow exponentially (since they double each level). In Python this is fine because integers have arbitrary precision, but in languages with fixed-width integers, you may need to normalize positions by subtracting the first position at each level to prevent overflow.

Minimum Depth of Binary Tree

For LeetCode 111, the task is to find the minimum depth: the number of nodes along the shortest path from the root down to the nearest leaf node.

BFS is the ideal approach here because it visits levels in order, so the first time you encounter a leaf node, you have found the minimum depth. There is no need to explore the rest of the tree.

def min_depth(root):
    if not root:
        return 0
    queue = deque([(root, 1)])
    while queue:
        node, depth = queue.popleft()
        if not node.left and not node.right:
            return depth
        if node.left:
            queue.append((node.left, depth + 1))
        if node.right:
            queue.append((node.right, depth + 1))

This is a case where BFS has a genuine advantage over DFS. A DFS-based approach must visit the entire tree to be sure it has found the shallowest leaf. BFS can return early as soon as it hits the first leaf, which in a highly unbalanced tree can save significant work.

Add One Row to Tree

LeetCode 623. Add One Row to Tree asks you to insert a row of nodes with a given value at a specified depth. Every node at depth d - 1 gets new left and right children with the given value, and the original children become children of the newly inserted nodes.

BFS to the target depth minus one, then rewire. For each node at that level, create new nodes and splice them in between parent and children.

def addOneRow(root, val, depth):
    if depth == 1:
        new_root = TreeNode(val)
        new_root.left = root
        return new_root
    queue = deque([root])
    for _ in range(depth - 2):
        for _ in range(len(queue)):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    for node in queue:
        new_left = TreeNode(val)
        new_right = TreeNode(val)
        new_left.left = node.left
        new_right.right = node.right
        node.left = new_left
        node.right = new_right
    return root

The BFS runs to depth d - 2 levels (since the root is depth 1), leaving the queue holding all nodes at depth d - 1. Then we iterate over those nodes and insert the new row. The special case at the top handles inserting above the root. Time is $O(n)$ and space is $O(w)$ for the queue width.

When DFS Works Just as Well

Not every level-related problem needs BFS. For maximum depth (LeetCode 104), a simple recursive DFS is clean and efficient:

def max_depth(root):
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

This works because maximum depth requires visiting every node regardless, so BFS's early-termination advantage does not apply. DFS with depth tracking also works well for problems like "find all nodes at depth k" or "check if a tree is balanced," where you need the depth but do not need to group nodes by level.

The rule of thumb: use BFS when you need to process level by level, need to find the shallowest occurrence of something, or need to link nodes within the same level. Use DFS when you need to aggregate information bottom-up (like subtree sums or heights) or when the problem naturally decomposes into left and right subproblems.

Complexity Analysis

BFS level-order traversal runs in $O(n)$ time, where n is the number of nodes, because each node is enqueued and dequeued exactly once. The space complexity is $O(w)$, where w is the maximum width of the tree. For a complete binary tree, the last level has roughly $n/2$ nodes, so the queue can hold up to $O(n)$ nodes. For a completely skewed tree (essentially a linked list), the width is 1, so the space is $O(1)$ beyond the queue overhead.

DFS-based alternatives use $O(h)$ space for the recursion stack, where h is the tree height. For a balanced tree, h = $O(\log n)$, which is better than BFS's $O(n)$ space. For a skewed tree, h = $O(n)$, which is the same as BFS's $O(1)$ width case but in the opposite direction. Choosing between BFS and DFS sometimes comes down to which dimension (width vs. height) is smaller for the expected input shape.

Recognizing this pattern

You're probably looking at BFS level-order traversal when:

• The problem asks you to process a tree level by level, or group output as a list of lists by depth.
• You need the shallowest occurrence of something, such as minimum depth or the first node satisfying a predicate, where early termination at a level matters.
• The answer depends on left-to-right ordering within a level (right-side view, zigzag, level averages, next-right pointers).
• DFS would force you to reconstruct level grouping after the fact, while a queue gives it to you for free.

Common templates:

• Level-batched queue: at each step, snapshot len(queue) and process exactly that many nodes. Example: Binary Tree Level Order Traversal.
• Right-side / boundary view: keep the last (or first) node enqueued per level. Example: Binary Tree Right Side View.
• Zigzag alternation: reverse the level list on odd depths. Example: Binary Tree Zigzag Level Order Traversal.
• Early-exit minimum depth: return as soon as you dequeue a leaf. Example: Minimum Depth of Binary Tree.