Introduction to Level Order Traversal Pattern

You are given a binary tree. Return its values grouped by level, so the root is the first group, its children are the second, and so on.

        1
      /   \
     2     3          becomes   [[1], [2, 3], [4, 5, 6]]
    / \     \
   4   5     6

Recursion is the usual way to walk a tree, and here it works against you. A recursive walk goes deep along one branch before coming back, so it meets node 4 before node 3. The values arrive in the wrong order for this question.

What you need is the opposite. Visit everything at depth 1, then everything at depth 2, and never skip ahead.

A queue gives you that. It hands back items in the order they arrived. So if you add the children of every node you visit, the nodes come out in depth order on their own.

One detail turns that into levels rather than a flat list. Before starting a level, record how many nodes are in the queue. That count is exactly the size of the current level, because nothing else has been added yet.

Core idea

The Level Order Traversal pattern walks a tree with a queue, one whole level per round.

The queue produces depth order on its own. Measuring the queue at the start of each round is what turns that stream into separate levels.

How it works

1. Put the root into a queue. Stop early if the tree is empty.
2. While the queue is not empty, start a new round.
3. Record levelSize as the number of nodes currently in the queue.
4. Remove exactly levelSize nodes. For each one, record its value and add its children to the back.
5. The values collected in that round are one complete level.
6. Repeat until the queue is empty.

Every node is added once and removed once, so the time is O(N). The queue holds at most one level at a time, so the space is O(W) where W is the widest level. For a balanced tree that is about N/2.

Step 3 is the whole pattern. Read the size before the inner loop, because the loop is adding children to the same queue as it runs.

Recognize it when

Use Level Order Traversal when the question shows these signs.

• The wording names a level, a row, a depth, or a generation.
• You need one answer per level, such as a maximum, an average, or a sum.
• The output is a list of lists, one per level.
• The question is about the shape of the tree, such as how wide it is.
• Your first idea is recursion, and recursion visits the nodes in an order that does not help.

It is not this pattern when:

• The question is about a path from root to leaf, or about a subtree. Depth First Search follows paths naturally.
• Order does not matter at all and you only need a count or a sum over every node. Either traversal works, so use the simpler one.
• The structure is a graph with cycles. The same queue is used there, but you must also track which nodes have been visited.

The template

function levelOrder(root):
    if root is empty:
        return empty list

    result = empty list
    queue  = new queue containing root

    while queue is not empty:
        levelSize = size of queue         # read it BEFORE the inner loop
        level     = empty list

        repeat levelSize times:
            node = remove from front of queue
            append node.value to level
            if node.left  is not empty: add node.left  to back of queue
            if node.right is not empty: add node.right to back of queue

        append level to result

    return result

Almost every problem in this chapter is this loop with a different line in the middle. Collecting values gives you level lists. Keeping a running maximum gives you the largest value per level. Reversing result at the end gives you bottom-up order.

Variants in this chapter

Maximum Width is the one that surprises people. Counting the nodes in a level is not enough, because gaps count towards the width. Each node has to carry a position number.

Watch out for

• Reading the queue size inside the loop. The inner loop adds children as it runs, so the size changes while you are using it. Capture it once, before the round starts.
• Adding empty children. Pushing a missing child fills the queue with nothing and breaks every level count that follows.
• Using a plain list as a queue. Removing from the front of an array is O(N) in most languages, which quietly turns the whole traversal into O(N²). Use a real queue or an index pointer.
• Forgetting the empty tree. A missing root must return an empty result rather than a list holding one empty level.
• Measuring width by counting. Width is the distance between the first and last positions on a level, including the empty places between them.

How this compares with nearby patterns

Tree Breadth First Search, the next chapter, uses this exact queue loop. The two chapters share the same traversal and even share two of their problems. Read this one for the shape of a level, and read that one for what the depth ordering lets you answer.

Key Takeaways

• A queue visits a tree in depth order without any extra effort.
• Recording the queue size at the start of a round is what separates one level from the next.
• Time is O(N) and space is O(W), the width of the widest level.
• Never add an empty child, and never use an array as a queue.
• Most problems here change one line inside the round, not the loop around it.

Let's apply it to the first problem, Reverse Level Order Traversal.