GitHub

Binary Tree Level Order Traversal medium

Description

Given the root of a binary tree, return the level order traversal of its nodes’ values — that is, the values grouped layer-by-layer from left to right, top to bottom.

Examples

> Case 1:
    Input:        3
                 / \
                9  20
                  /  \
                 15   7
    Output: [[3], [9, 20], [15, 7]]
 
> Case 2:
    Input:  [1]
    Output: [[1]]
 
> Case 3:
    Input:  []
    Output: []

Constraints

0 <= number of nodes <= 2000
-1000 <= node.val <= 1000

Intuition — BFS with the snapshot trick

This is the canonical use of breadth-first search on a tree. We use a queue, and the key trick is the size snapshot:

At the top of each iteration of the outer loop, snapshot the queue’s current size. That count is exactly the number of nodes in the current level. Process that many nodes — they all become one “level” array — and the children they enqueued become the next level for the following iteration.

That snapshot is what turns generic BFS into level-aware BFS. Without it, you can’t tell where one layer ends and the next begins.

Code

⚠️

The snapshot has to happen before the inner loop, not inside it. If you write for (int i = 0; i < q.size(); i++), the queue grows mid-loop as we push children, and your “level” will spill over into the next layer. Save the size to a local variable first.

Why this template is so reusable

Once you have level-aware BFS, dozens of problems collapse to a one-line tweak:

Problem	Tweak inside the level loop
Average of Levels in Binary Tree	Track sum + count; append sum/count to result.
Binary Tree Right Side View	Only record the last node of each level.
Binary Tree Left Side View	Only record the first node of each level.
Binary Tree Zigzag Level Order	Reverse the level array on alternating levels.
Maximum Depth of Binary Tree	Just count the number of outer iterations.
Minimum Depth of Binary Tree	Return as soon as you hit a leaf — that’s the shortest.
Populating Next Right Pointers	Wire siblings within the level loop.

The template is the same; only the work-per-level changes.

Recursive variant — also clean

You can build the level array via recursion, passing the current depth down:

def level_order(root):
    levels = []
    def walk(node, depth):
        if node is None: return
        if len(levels) == depth:
            levels.append([])                    # first time at this depth
        levels[depth].append(node.val)
        walk(node.left,  depth + 1)
        walk(node.right, depth + 1)
    walk(root, 0)
    return levels

This is a preorder DFS that knows the depth, not BFS — but the output is the same. Whether you find BFS or DFS more natural is taste. BFS is more idiomatic for “level” problems.

Analysis

Time: O(n) — every node enqueued and dequeued exactly once.
Space: O(w) for the queue, where w is the maximum width. The output is necessarily O(n) too.

Diameter of Binary Tree Validate BST