Binary Tree Level Order Traversal: BFS with a Queue

Given the root of a binary tree, return the level order traversal of its nodes' values. That means collecting values from left to right, level by level. This is LeetCode 102: Binary Tree Level Order Traversal, and it is the definitive introduction to BFS on trees.

Why BFS?

Level order traversal is all about processing a tree layer by layer. DFS (depth-first search) dives deep into one branch before backtracking, which makes it awkward for grouping nodes by level. BFS (breadth-first search) naturally visits nodes in level order because it uses a queue: first in, first out.

The trick is knowing how many nodes belong to the current level. At the start of each level, you snapshot the queue size. That tells you exactly how many nodes to dequeue before moving on. Everything you enqueue during that pass belongs to the next level.

The BFS solution

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

Here is what each part does:

• queue = deque([root]) seeds the queue with the root node. Level 0 always has exactly one node.
• level_size = len(queue) captures how many nodes are in the current level before we start dequeuing.
• The for loop dequeues exactly level_size nodes, collects their values, and enqueues their children. When the loop finishes, the queue holds only nodes from the next level.
• result.append(level) stores the completed level list and moves on.

Visual walkthrough

Let's trace BFS through the tree [3, 9, 20, null, null, 15, 7]. Watch how the queue drains one level at a time, and the output list builds up level by level.

Notice the rhythm. At each step, you drain the entire current level from the queue, collect the values, and push children for the next level. Once the queue is empty, every level has been captured.

Common mistakes

Forgetting the level size snapshot. If you just loop while queue without capturing len(queue) first, you will mix nodes from different levels into the same list. The snapshot is what separates one level from the next.

Using a list instead of a deque. Calling list.pop(0) works, but it is O(n) per operation because every remaining element shifts. A deque gives you O(1) popleft. On large trees this difference matters.

Not handling the empty tree. If root is None and you try to seed the queue with it, you will process a None node and crash. Always check for an empty tree up front.

Complexity analysis

The space is O(n) in the worst case because the bottom level of a complete binary tree contains roughly half of all nodes. For a skewed tree (a single chain), the queue never holds more than one node, so space is O(1). But we express the worst case as O(n).

Building blocks

This problem is built on one core pattern: BFS level-by-level processing. The template looks like this:

from collections import deque

def bfs_by_level(root):
    queue = deque([root])
    while queue:
        level_size = len(queue)
        for _ in range(level_size):
            node = queue.popleft()
            # process node
            for child in get_children(node):
                queue.append(child)

The snapshot level_size = len(queue) is what turns a plain BFS into a level-aware BFS. Once you internalize this template, you can apply it to a range of problems:

• Binary Tree Right Side View (LeetCode 199): same BFS, but only keep the last node of each level.
• Binary Tree Zigzag Level Order (LeetCode 103): same BFS, but reverse every other level list.
• Minimum Depth of Binary Tree (LeetCode 111): BFS by level, return the depth when you hit the first leaf.
• Average of Levels (LeetCode 637): same BFS, compute the mean of each level list instead of collecting it.

All of these are variations on the same brick. Learn the level-by-level BFS template, and each variation is a small tweak.

Edge cases

• Empty tree (root is None): return an empty list []. The guard clause at the top handles this.
• Single node (no children): return [[root.val]]. The queue starts with one node, processes it, finds no children, and the loop ends after one level.
• Skewed tree (every node has only one child): each level has exactly one node, so the result is [[a], [b], [c], ...]. The algorithm handles this without any special logic.

From understanding to recall

You just read through a clean BFS solution and watched the queue drain level by level. It makes sense right now. But when you face Binary Tree Right Side View or Zigzag Traversal in an interview next month, will you remember the level_size = len(queue) snapshot? Will you reconstruct the template from scratch without hesitation?

Understanding a pattern and being able to reproduce it under pressure are different skills. Spaced repetition bridges that gap. You practice typing the BFS level-by-level template from memory at increasing intervals. First after a day, then three days, then a week. Each repetition reinforces the snapshot trick, the deque usage, and the inner loop structure until it becomes automatic.

BFS level-by-level is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Maximum Depth of Binary Tree - The best introduction to tree recursion, which also shows BFS as an alternative approach
• Number of Islands - BFS applied to a 2D grid instead of a tree, reinforcing the queue-based exploration pattern