Binary Tree Level Order Traversal

If you visit every node but mix adjacent depths, the traversal is still wrong. The key is to make the queue represent one level at a time.

Read the output contract first

The function receives the root of a binary tree and returns a list of lists:

• The outer list is ordered from the root downward.
• Each inner list contains values from one depth.
• Values inside a level appear from left to right.
• An empty tree produces [].

For this tree:

        1
       / \
      2   3
     / \
    4   5

the output is:

[[1], [2, 3], [4, 5]]

A flat traversal such as [1, 2, 3, 4, 5] is not enough. The grouping by depth is part of the result contract.

That contract gives us the first solution direction: process the shallowest unfinished nodes first, preserve their left-to-right order, and collect exactly one depth into each result list.

Recognize the breadth-first pattern

The output is organized by distance from the root. That is the structural signal for breadth-first search, or BFS.

A queue models the traversal frontier:

1. Put the root in the queue.
2. Remove the current level from left to right.
3. Add those nodes’ children to the back of the queue.
4. The children now form the next level.

The queue behaves like a moving boundary. Older nodes are processed first; newly discovered children wait behind them.

A depth-first search can also solve the problem by carrying a depth argument and appending each value into a depth-indexed list. That approach is valid, but the queue-based version exposes the level boundary directly. For this output contract, that visibility is useful in an interview: the data structure mirrors the requirement.

Node values do not influence the algorithm. They may be negative, duplicated, or arranged in any order. The tree structure determines traversal order, not value comparisons. Tree balance is irrelevant too; a one-sided tree must work just as well as a full tree.

Derive the queue algorithm from its obligations

The implementation has three obligations.

1. Preserve left-to-right order

When processing a node, enqueue its left child before its right child:

if node.left:
    queue.append(node.left)
if node.right:
    queue.append(node.right)

Because the queue is FIFO, this order becomes the order in which the next level is processed.

2. Isolate one level

At the beginning of an outer loop, save the current queue length:

level_size = len(queue)

That number tells us how many nodes belong to the current level. We then process exactly that many nodes.

This saved boundary is the most important detail in the solution. While processing the current level, we append children to the queue. Those children belong to the next level, so they must not be consumed by the current level’s loop.

3. Build the next frontier

For every node in the current level:

• remove it from the front,
• append its value to the current result list,
• enqueue its existing children.

After exactly level_size removals, the current level is complete and the queue contains the next level.

Algorithm

1. If root is None, return [].
2. Initialize a queue with root.
3. While the queue is not empty:
   1. Save the current queue length as level_size.
   2. Create an empty list for this level.
   3. Repeat level_size times:
      • remove one node,
      • record its value,
      • enqueue its left child if present,
      • enqueue its right child if present.
   4. Append the completed level to the result.
4. Return the result.

Pseudocode:

result = []
queue = [root]

while queue is not empty:
    level_size = number of nodes currently in queue
    level = []

    repeat level_size times:
        node = remove the front node
        append node.value to level

        if node.left exists:
            add node.left to queue
        if node.right exists:
            add node.right to queue

    append level to result

return result

The queue length is not merely a convenient loop count. It is the explicit boundary between “nodes being emitted now” and “nodes discovered for later.”

Dry-run the frontier boundary

Use this tree:

        3
       / \
      9   20
         /  \
        15   7

The expected result is:

[[3], [9, 20], [15, 7]]

Here is the state transition:

Outer iteration	Queue at start	Saved size	Current level	Queue after processing
1	[3]	1	[3]	[9, 20]
2	[9, 20]	2	[9, 20]	[15, 7]
3	[15, 7]	2	[15, 7]	[]

Look closely at the second iteration:

• The queue starts as [9, 20].
• level_size is saved as 2.
• Processing 9 adds no children.
• Processing 20 adds 15 and 7.
• The queue temporarily becomes [15, 7].
• The loop still stops after two removals because the saved size was 2.

That is the boundary working correctly. The newly enqueued children wait for the next outer iteration.

A common mistake is to process a level with a loop like this:

while queue:
    node = queue.popleft()
    level.append(node.val)

    if node.left:
        queue.append(node.left)
    if node.right:
        queue.append(node.right)

This loop does visit every node, but it has no boundary. Once it removes the current level’s nodes, it immediately continues into their children, then their grandchildren, and so on. The result collapses multiple depths into one list.

The queue alone gives you breadth-first visitation. The saved queue length gives you grouped breadth-first visitation.

Implement the Python solution cleanly

Use collections.deque for the queue. Removing from the front of a deque is constant time. A Python list is efficient at its right end, but repeatedly calling pop(0) shifts the remaining elements and adds unnecessary work.

from collections import deque


class Solution:
    def levelOrder(self, root):
        if root is None:
            return []

        result = []
        queue = deque([root])

        while queue:
            level = []
            level_size = len(queue)

            for _ in range(level_size):
                node = queue.popleft()
                level.append(node.val)

                if node.left is not None:
                    queue.append(node.left)

                if node.right is not None:
                    queue.append(node.right)

            result.append(level)

        return result

The judge usually supplies the TreeNode definition, so the solution method only needs to use the expected val, left, and right attributes.

Each variable has a specific job:

• result stores all completed levels.
• queue stores the current frontier and, during processing, the next frontier.
• level_size freezes the current level’s boundary.
• level stores values for exactly one depth.

Keep level as a new list on every outer iteration. Do not reuse one mutable list and append it repeatedly:

# Avoid this pattern
level = []

while queue:
    # mutate level
    result.append(level)

If the same list object is reused, later mutations can make earlier result entries appear to change too. One level, one list, one append.

Prove correctness and analyze cost

The useful invariant is:

At the start of every outer-loop iteration, the queue contains exactly the nodes at one depth, in left-to-right order.

Base case

Before the first iteration, the queue contains only root. That is exactly depth zero, in the correct order.

Inductive step

Assume the queue contains one complete level in left-to-right order.

The algorithm saves its length as level_size and removes exactly that many nodes. Therefore:

• every node from the current level is processed,
• no child from the next level is processed during this iteration.

For each removed node, the algorithm enqueues the left child before the right child. Since current-level nodes are themselves removed left to right, their children enter the queue in the correct left-to-right order for the next level.

After level_size removals, the queue therefore contains exactly the next nonempty level, in left-to-right order. The invariant holds for the next iteration.

When the queue becomes empty, every node has been emitted into the correct inner list. The returned result is complete and correctly ordered.

Complexity

Let n be the number of nodes and w be the maximum number of nodes at any one depth.

• Time: O(n). Every node enters the queue once, leaves the queue once, and performs constant work while processed.
• Auxiliary space: O(w) for the queue.
• Output space: O(n) in total because every node value appears in the returned result.

The auxiliary queue is O(w), which is O(n) in the worst case. A broad tree can have a large frontier; a skewed tree has a frontier of size one.

If an interviewer asks for total space including the returned result, state O(n). If they ask for auxiliary space excluding output, state O(w).

Edge cases and interview failure modes

Test the shape, not just the happy-path example.

Empty tree

root = None

Return:

[]

Do not return [[]] or None. There is no depth to represent.

Single-node tree

    8

Return:

[[8]]

The root still occupies one level.

Skewed tree

1
 \
  2
   \
    3

Return:

[[1], [2], [3]]

Do not assume that a node has two children or that the tree is balanced.

Negative and duplicate values

Values must be copied unchanged. They do not affect ordering:

[[-2], [5, 5], [-2]]

The structure determines where each value belongs.

Common implementation mistakes

• Using queue.pop(0) instead of deque.popleft().
• Forgetting to save the queue length before processing a level.
• Saving the length but recalculating len(queue) inside the loop.
• Enqueuing None children, which creates fake work and can cause attribute errors.
• Enqueueing the right child before the left child.
• Reusing the same mutable level list for every result entry.
• Returning a flat list because the code visits nodes correctly but ignores the output shape.

When debugging, print the queue at the start of each outer iteration and print the saved level_size. If those two values do not describe one depth, the invariant has already failed.

The transferable recognition rule

When an output or operation is organized by depth, distance, or nearest frontier, ask whether the queue should represent the current boundary.

Then ask one precise question before writing code:

What exactly does the queue contain at the start of one outer iteration?

For this problem, the answer is: one complete level, ordered from left to right. The saved queue length protects that statement while children are added.

That is the reusable part of the Binary Tree Level Order Traversal solution. Do not memorize the loop as a ritual. Derive it from the boundary:

• queue holds the current level,
• fixed length marks where the level ends,
• left-before-right preserves order,
• children form the next frontier.

DFS is often the better fit when a subtree must return a value upward or when path-specific state travels downward. Here, the required state moves sideways across a frontier, so BFS makes the structure visible.

Before submitting, explain out loud why level_size = len(queue) is evaluated once per level. If that explanation is clear, the implementation is usually clear too.