Level-Order Traversal: The Queue Trick Every Interview Tests

Pull up LeetCode and filter for trees. About half the medium-difficulty problems there are the same algorithm in different clothes. Queue, level-size snapshot, inner loop. Once you see the pattern, you cannot unsee it. Interviewers know this too, which is why you'll keep meeting it.

Level-order traversal is BFS applied to a tree. It visits nodes row by row, left to right. The algorithm fits in ten lines. This post covers the core idea, every interview variation built on top of it, and clean implementations in 14 languages.

Why a Queue and Not a Stack?

Depth-first traversal uses a stack (either the call stack via recursion, or an explicit one). Last-in-first-out drills down one path before backtracking.

Level-order needs the opposite. You want to finish the current row before moving to the next. A queue's first-in-first-out property is exactly what enforces that order. Enqueue the root, then for each node you dequeue, enqueue its children. Children of the current level line up behind the remaining nodes at this level, so they get processed after the whole row is done.

No fancy data structures. Just a queue and a loop.

Queue, Loop, Repeat

1. Enqueue root
2. While queue is not empty:
   a. Dequeue a node, process it
   b. Enqueue its left child (if it exists)
   c. Enqueue its right child (if it exists)

Every node is enqueued once and dequeued once. Time is O(n). Space is O(w) where w is the maximum width of the tree.

For a flat traversal where you just need nodes in level order without caring which level they came from, this loop is enough. But most interview problems want results grouped by level, which requires one small addition.

The Level-Size Snapshot: The Trick Interviewers Are Actually Testing

The bare BFS loop gives you nodes in level order, but it does not tell you where one level ends and the next begins. To group results by level, you need to process exactly one level at a time.

Snapshot len(queue) at the start of each outer loop iteration. That count is the exact number of nodes on the current level. Process that many nodes in an inner loop, then whatever you enqueued during those iterations belongs to the next level.

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

This pattern is the foundation for every level-order interview problem. Once you have it, the variations fall into place. The seven problems in the next section are all this loop with one small thing changed.

Queue at the start of each outer iteration holds exactly one level's nodes

The queue at the start of each outer iteration holds exactly one level's nodes. level_size = len(queue) captures that count before the inner loop runs.

Level Order Traversal: Time and Space Complexity

Time: O(n). Every node is enqueued exactly once and dequeued exactly once. Work per node is constant, so total is linear.

Space: O(w) where w is the maximum width, meaning the maximum number of nodes on any single level.

Two extremes worth thinking through. A perfect binary tree's last level holds roughly n/2 nodes, so the queue at peak holds all of them. Worst-case space is O(n). A skewed tree (effectively a linked list) has one node per level, so the queue never holds more than one. Space is O(1).

Compare that to DFS, which uses O(h) stack space. On a balanced tree h = O(log n), which beats level-order's worst case. On a skewed tree h = O(n), same as level-order. Neither dominates. The choice depends on what the problem asks for, which is covered more in BFS vs DFS.

Seven Problems. One Algorithm.

Once you have the level-size snapshot pattern, these seven problem types are all variations on the same core loop. Interviewers call them different problems. They are not.

1. Basic Level Order (LeetCode 102)

Return a list of lists where each inner list contains values at one level. The code above implements this directly.

2. Zigzag Level Order (LeetCode 103)

Alternate direction each level: left-to-right on even levels, right-to-left on odd. Use a deque for the level buffer. On left-to-right levels, append to the right. On right-to-left levels, append to the left. The BFS queue stays the same.

from collections import deque

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

3. Right Side View (LeetCode 199)

Return the last node visible from the right. With the level-size snapshot, the answer is the last node in each level's inner loop.

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

4. Average of Levels (LeetCode 637)

Sum all values on a level, divide by the count. Straightforward with the inner loop.

def average_of_levels(root):
    result = []
    queue = 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

5. Maximum Depth (LeetCode 104)

Count the number of levels. Increment a depth counter once per outer loop iteration.

def max_depth(root):
    if not root:
        return 0
    depth = 0
    queue = deque([root])
    while queue:
        level_size = len(queue)
        depth += 1
        for _ in range(level_size):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return depth

6. Minimum Depth (LeetCode 111)

Return as soon as you find the first leaf, not after processing the whole tree. This is where BFS genuinely beats DFS. BFS finds the nearest leaf first by definition.

def min_depth(root):
    if not root:
        return 0
    depth = 0
    queue = deque([root])
    while queue:
        level_size = len(queue)
        depth += 1
        for _ in range(level_size):
            node = queue.popleft()
            if not node.left and not node.right:
                return depth
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return depth

7. Populating Next Right Pointers (LeetCode 116/117)

Connect each node to its right neighbor on the same level. Within each level's inner loop, keep a reference to the previous node and set prev.next = node. Reset prev to None at the start of each level.

def connect(root):
    if not root:
        return root
    queue = deque([root])
    while queue:
        level_size = len(queue)
        prev = None
        for _ in range(level_size):
            node = queue.popleft()
            if prev:
                prev.next = node
            prev = node
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return root

LeetCode 116 guarantees a perfect binary tree. LeetCode 117 extends this to arbitrary trees. The same code handles both.

What Goes Wrong in Interviews

Using a stack instead of a queue. Reach for a stack when you're nervous and you get DFS. The traversal order is wrong. On a two-node tree it looks almost right, which is the worst kind of wrong. The queue is not incidental. It is the whole mechanism.

Forgetting to snapshot level size. Write while queue with only an outer loop and no inner loop tracking level size, and you get a flat list of values, not a list of lists. On problems like LeetCode 102, the output format will be wrong even if the values are in the right order.

Using list.pop(0) in Python. Removing from the front of a Python list is O(n) because every remaining element shifts left. LeetCode's test trees are small enough that it passes anyway, so you might not notice until someone reviews your code. Use collections.deque and popleft(). Same traversal, O(1) dequeue.

Off-by-one on minimum depth. A node with only a left child is not a leaf. Only nodes with no children count. LeetCode 111 will catch this if you get it wrong.

If you want to drill these patterns live, SpaceComplexity runs voice mock interviews with rubric-based feedback across problem-solving, communication, and code quality. Catching a bug in your explanation is different from catching it in a silent editor.

For more on what interviewers score during the session, read what interviewers write while you think.

One Structure, Every Language

All 14 implementations return a list of lists: each inner list holds the values at one level, left to right. Each snippet includes the TreeNode definition so it runs standalone.

from collections import deque
from typing import Optional, List

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def level_order(root: Optional[TreeNode]) -> List[List[int]]:
    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