Binary Tree Level Order Traversal

PracticeNeetCode ↗LeetCode ↗

Given the root of a binary tree, return the values of its nodes grouped level by level, from top to bottom.

Example

Key Pointers

• BFS with a queue naturally processes one level at a time, as long as you snapshot the queue's length before draining it.
• Recording len(queue) at the start of each level, then popping exactly that many nodes, is what keeps levels from blending together.
• Enqueue each node's children as you dequeue it, so the next level builds up while the current one is being collected.

Step-by-Step Analysis

1. If root is None, return [].
2. Initialize a queue holding root, and an empty result list.
3. While the queue isn't empty, record its current length as level_size.
4. Pop level_size nodes, collecting their values into a level list and enqueuing each node's children.
5. Append the level list to result; repeat until the queue is empty.

Complexity

Time: O(n) — Space: O(n)

Code

from collections import deque

def levelOrder(root: TreeNode | None) -> 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

Code Explanation

How the solution above works, piece by piece.

1. if not root: return []: an empty tree has no levels.
2. queue = deque([root]): a queue gives nodes back in the order they were added, which is what keeps levels in order. deque.popleft() is O(1).
3. while queue: one pass of this loop handles exactly one level.
4. level_size = len(queue): read the size before popping. At this moment the queue holds only the current level; children added below belong to the next level and must not be counted.
5. Pop level_size nodes, add each value to level, and push its left and right children (if any) onto the back of the queue.
6. result.append(level): one inner list per level. Every node is pushed and popped once: O(n) time, O(width) queue space.

Visual Walkthrough

Running it on root = [3, 9, 20, null, null, 15, 7]:

Video Explanation

NeetCode — Binary Tree Level Order Traversal, LeetCode 102