Binary Tree Level Order Traversal

Given a binary tree, return its values grouped level by level (a BFS traversal, top to bottom).

Example

Input: 3 9 20 null null 15 7 Output: 3 | 9 20 | 15 7

Approach

BFS with a queue, but process it one level at a time: capture the queue's current size before the inner loop, so you know exactly how many nodes belong to this level versus the next one — a small but essential detail that separates "level order" from a plain BFS that just visits nodes one at a time with no level boundaries.

Walkthrough

Tree: root 3, left child 9, right child 20; 20's children are 15 and 7.

1def level_order(root):
2    result = []
3    queue = [root] if root else []
4    while queue:
5        level_size = len(queue)
6        level = []
7        for _ in range(level_size):
8            node = queue.pop(0)
9            level.append(node.val)
10            if node.left:
11                queue.append(node.left)
12            if node.right:
13                queue.append(node.right)
14        result.append(level)
15    return result

Input format

Line 1: the tree in level-order, space-separated, null for missing children

Print each level's values space-separated, with levels separated by |.