Binary Tree Level Order Traversal

Difficulty: Medium

Problem

Given the root of a binary tree, return its node values grouped by level, as a list of lists: the first inner list holds every value at depth 0, the second holds every value at depth 1, and so on. Go from the top down and read each level left to right. This row-by-row exploration is called BFS (Breadth-First Search), and it is a fundamentally different way to explore a tree than the DFS recursion you've learned so far: instead of diving deep down one branch, we sweep across one full level at a time.

Example

Input: root = [1,2,3,4,null,null,5]
Output: [[1],[2,3],[4,5]]
Explanation: The tree has three levels. Level 0 is just the root: [1]. Level 1 is [2, 3], read left to right. Level 2 is [4, 5]: 4 is the left child of 2 and 5 is the right child of 3. Each level becomes its own inner list.

Brute-force approach

There is no meaningful 'brute force vs optimal' split here. BFS with a queue IS the natural solution. Trees skip straight to the optimal approach.

Optimal approach

Key insight: A queue is first-in-first-out, so nodes are served in exactly the order they were discovered, and we discover all of level d before anything at level d+1, so the queue hands us the tree level by level. The len(queue) snapshot at the top of each round marks exactly where one level ends and the next begins.

Explore the tree in waves with a queue: snapshot the queue's size, dequeue exactly that many nodes into the current level's list, and enqueue their children, they form the next wave.

Steps

If the root is null, return an empty list, no tree, no levels
Create an empty result list and a queue seeded with the root
While the queue isn't empty, snapshot levelSize = len(queue)
Dequeue exactly levelSize nodes, appending each value to a fresh level list
As each node is dequeued, enqueue its children at the back, they form the next level
Append the level list to result; when the queue runs dry, return result

Time complexity: O(n) · Space complexity: O(w) where w = maximum width of the tree

Pseudocode

function levelOrder(root):
    if root is null:
        return []
    
    result = []
    queue = [____]
    
    while queue is not empty:
        levelSize = ____
        level = []
        
        repeat levelSize times:
            node = queue.dequeueFront()
            level.append(node.val)
            if node.left exists:  queue.enqueueBack(node.____)
            if node.right exists: queue.enqueueBack(node.____)
        
        result.append(level)
    
    return result

Hints

Seed the queue: BFS starts the waiting line with exactly one node, which one?
The snapshot: at the top of each round, how many nodes are standing in the queue? That count IS the current level's size.
The two enqueues: which two child pointers join the BACK of the line? (Left before right keeps each level reading left to right.)
Children never go into the current level's list: they wait in the queue for the NEXT round. Only the values dequeued this round belong to this level.

Complexity questions

What is the time complexity of BFS level order traversal on a tree with n nodes?

O(n). Every node is enqueued exactly once and dequeued exactly once, and each visit does O(1) work: record a value, enqueue up to two children. Total: O(n), assuming the dequeue itself is O(1), which is exactly why the data structure choice matters (see question 3!).

BFS uses O(w) extra space, where w is the widest level. Which tree SHAPE makes the queue biggest?

A bushy, perfect tree: its last level alone holds about n/2 nodes. The queue's peak is one full level, so the widest tree is the worst: a perfect tree's bottom level packs about n/2 nodes, making BFS space O(n). Notice the lovely contrast: a SKEWED tree, the worst case for DFS recursion (O(n) call stack), is BFS's best case, because every level holds just one node and the queue stays tiny. DFS suffers on skewed trees; BFS suffers on bushy ones.

Our teaching code used queue.pop(0) on a Python list. Why is that O(n) per call, and what fixes it?

Removing index 0 shifts every remaining element one slot left; the fix is collections.deque, whose popleft() is O(1). Python lists are arrays: removing the first element forces every remaining element to shift one slot left, costing O(n) per pop, on wide trees the traversal can degrade toward O(n²). collections.deque is a double-ended queue where popleft() and append() are both O(1), restoring the clean O(n) total. Same algorithm, better engine.

A matching node sits just 2 levels deep in a huge tree. Which traversal is guaranteed to find the SHALLOWEST match first, and why?

BFS: it exhausts every node at depths 0, 1, 2 before EVER touching depth 3, so the first match it finds is the shallowest one. BFS explores strictly in increasing depth order, it finishes each depth completely before going deeper, so the first match it encounters is guaranteed to be the shallowest. DFS makes no such promise: it might wander 50 levels down the wrong branch before backtracking. This is exactly why BFS becomes the shortest-path algorithm when you meet unweighted graphs later.

Check your understanding of Binary Tree Level Order Traversal

What does 'level order' actually mean?

Visit every node at depth 0, then every node at depth 1, then depth 2. Row by row, left to right. Level order means breadth-first: finish an entire row before starting the next, reading each row left to right. Contrast that with the DFS you know, which dives deep down one branch (3 → 9) before ever glancing at 20's side. Here we visit 3, then BOTH of 9 and 20, then both of 15 and 7.

What is the level order traversal of [3,9,20,null,null,15,7]?

[[3], [9, 20], [15, 7]]. Level 0 is just the root: [3]. Level 1 is [9, 20] left to right, and level 2 is [15, 7]. Both are 20's children, since 9 has none. The problem asks for each level as its OWN inner list, not one flat list, not one-node-per-list DFS order, and not bottom-up.

Which data structure powers BFS, and why?

A queue: first in, first out, so nodes are served in the exact order they were discovered. A queue is First-In-First-Out: nodes get served in exactly the order they were discovered, and since we discover a whole level before the next one, that IS level order. Careful with the stack option: a stack serves the NEWEST discovery first, so you'd dive deep and get DFS instead! The container decides the traversal.

All levels share ONE queue. How do we know where one level ends and the next begins?

Snapshot len(queue) at the start of each round: exactly that many nodes belong to the current level. At the moment a round starts, the queue holds the current level and nothing else: exactly [9, 20] when level 1 begins. So len(queue) taken right then is a perfect count: serve exactly that many nodes and stop, even as their children slip into the back mid-round. That frozen snapshot IS the boundary between levels.

When we dequeue a node, what do we do with its children?

Append them to the BACK of the queue. They'll be processed in the NEXT level's round. Children join the BACK of the line. Because each round only serves the snapshot count, fresh arrivals like 15 and 7 simply wait behind the current level. They get served in the next round, which is exactly the next level. Pushing them to the front would let grandchildren cut ahead and wreck the level order.