Binary Tree Level Order Traversal
Visit a tree level by level with BFS, using the queue's size to know where each level ends
Problem Statement
Given the root of a binary tree, return its level order traversal — the node values grouped by depth, from left to right.
Input: 3
/ \
9 20
/ \
15 7
Output: [[3], [9, 20], [15, 7]]
Input: root = []
Output: []Intuition
Depth-first traversal (the natural recursive one) dives down one branch before touching the next, so it visits 3, 9, 20, 15, 7 in an order that mixes levels together. This problem wants the opposite: everything at depth 0, then everything at depth 1, and so on.
The key insight
Use a queue — first in, first out. Enqueue the root. Then repeatedly dequeue a node and enqueue its children.
Because children are always added behind everything already waiting, the queue drains in exact depth order. Nodes at depth d are all processed before any node at depth d + 1.
That gives the right order, but the output has to be grouped by level, and a flat queue does not say where one level ends.
The level-size trick
At the top of each round, record size = len(queue).
At that moment the queue holds exactly one complete level and nothing else. Processing precisely size nodes consumes that whole level; everything enqueued during the round belongs to the next one. No depth field, no sentinel values.
Real-world analogy
Handing out flyers building by building. You knock on every door on floor 1, noting the stairwells to floor 2, then do all of floor 2. You finish a floor completely before climbing.
Watch it run
[]Approach
Handle the empty tree
A null root means an empty result.
While the queue is non-empty
Record size = len(queue) — the width of the current level.
Process exactly size nodes
Dequeue each one, append its value to the current level's list, and enqueue its non-null children.
Solution
from collections import deque
from typing import Optional
class TreeNode:
def __init__(
self,
val: int = 0,
left: Optional["TreeNode"] = None,
right: Optional["TreeNode"] = None,
):
self.val = val
self.left = left
self.right = right
def level_order(root: Optional[TreeNode]) -> list[list[int]]:
"""Node values grouped by depth, left to right."""
if not root:
return []
result: list[list[int]] = []
queue = deque([root])
while queue:
size = len(queue) # the queue holds exactly one full level
level: list[int] = []
for _ in range(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 resultDo not use a plain list as a queue
Python: list.pop(0) is O(n) because every remaining element shifts left, making the traversal O(n²). collections.deque gives O(1) popleft.
TypeScript: Array.prototype.shift() has the same problem. Either keep a read index into the array, or build a fresh next array per level as above — which is both fast and clearer.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(n)
- Time — each node is enqueued once and dequeued once.
- Space — the queue holds at most one level. For a perfectly balanced tree the widest level has about
n / 2nodes, so the worst case isO(n). A completely unbalanced tree (a chain) keeps the queue at size 1, usingO(1).
BFS vs. DFS
| BFS (queue) | DFS (stack or recursion) | |
|---|---|---|
| Visit order | level by level | branch by branch |
| Finds shortest path in an unweighted graph | yes | no |
| Space | O(width) | O(depth) |
| Best for | level grouping, minimum steps | path enumeration, subtree computations |
Level order traversal is BFS. The same queue-plus-level-size pattern solves "minimum number of moves" problems on grids and graphs.
Edge Cases
Related Problems
- N-ary Tree Preorder Traversal — DFS, the other traversal family
- Find the Town Judge — graph reasoning without traversal
- Valid Parentheses — a stack (LIFO) versus this queue (FIFO)