LeetEye LeetEye
Medium Tree Traversal ~5 min

Binary Tree Level Order Traversal

trees binary-tree-level-order-traversal

Problem

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

Examples

Example 1
Input: root = [3,9,20,null,null,15,7]
Output: [[3], [9, 20], [15, 7]]
Example 2
Input: root = [1]
Output: [[1]]
Key Insight

Use BFS (Breadth-First Search). Process all nodes at current level before moving to the next.

BFS with level tracking: before processing, count queue size = level size. Process exactly that many nodes, adding children for next level.

How to Approach This Problem

Pattern Recognition: When you see keywords like binary tree level order traversal trees, think Tree Traversal.

Step-by-Step Reasoning

1 BFS is preferred for level-order because:
Answer: It naturally visits nodes level by level
Queue gives FIFO order. Nodes at level k are processed before level k+1.
2 BFS uses:
Answer: Queue
Queue ensures FIFO - first in, first out. First discovered nodes processed first.
3 To know when a level ends:
Answer: Count nodes at each level before processing
Before processing level k, queue contains exactly all level-k nodes. Count them, process exactly that many.
4 Within a level, nodes are processed:
Answer: Left to right
We add left child before right child. Queue preserves this order.
5 When processing a node, we add its children:
Answer: After processing the node
Add children to queue AFTER visiting node. They'll be processed in the next level.
6 If a level has no nodes:
Answer: This means we're done
If queue is empty at start of a level, there are no more nodes. Stop.

Solution

from collections import deque

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

Complexity Analysis

Time O(n)
Space O(w)

Master This Pattern

Build intuition with interactive MCQs. Practice Tree Traversal problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye