roadmap/trees/Binary Tree Level Order Traversal

Binary Tree Level Order Traversal

MediumAmazonGoogleMetaMicrosoft

Problem

Given the root of a binary tree, return the level order traversal of its nodes' values as a list of lists (i.e., from left to right, level by level).

Intuition — the key insight

BFS naturally processes nodes level by level. The key trick: at the START of each iteration, snapshot the current queue size. That tells you exactly how many nodes belong to the current level — process exactly that many before moving to the next level.

Approach

BFS with level snapshotting

Initialize queue with root. While queue not empty: record current size (= nodes at this level). Process exactly that many nodes, adding their children to the queue. Collect values into a level list and add to result.

Complexity

Time

O(n)

Space

O(n)

Every node is enqueued and dequeued exactly once — O(n). The queue holds at most one full level at a time. The widest level of a complete binary tree has n/2 nodes — O(n) space.

Solution code

Python

def levelOrder(self, root: TreeNode) -> List[List[int]]:
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)  # snapshot current level
        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

Edge cases to remember

⚠Empty tree: return empty list

⚠Single node: return [[root.val]]

⚠Skewed tree: each level has exactly one node

Hints

What pattern do you think this problem uses?