Level-Order Traversal (BFS)
Level-order traversal visits the nodes of a tree one level at a time, top to bottom, left to right within each level, instead of plunging depth-first into one branch first. It’s the tree-specific application of breadth-first search (BFS), and it’s the traversal you reach for whenever the question is about “levels,” “shortest path in an unweighted tree,” or “process nodes closest to the root first.”
Overview / How it works
Picture a company org chart with a CEO at the top, two VPs reporting to them, and a handful of managers reporting to the VPs. If you wanted to print the chart level by level — the CEO, then both VPs, then all the managers — you would not want to dive into one VP’s entire reporting chain before looking at the other VP. You want to finish the current level completely before moving to the next one. That’s exactly what level-order traversal does for a binary tree.
The trick that makes this efficient is a queue: a first-in-first-out (FIFO) structure. You push the root into the queue. Then, repeatedly, you pop a node from the front, record it, and push its children (if any) onto the back of the queue. Because a queue preserves order, children of the node you just visited always end up behind the still-unvisited nodes of the current level and in front of the next level’s nodes. The result is that nodes come out of the queue in exactly level order.
Contrast this with depth-first traversals (preorder, inorder, postorder), which use a stack (explicit or the call stack via recursion) and plunge all the way down one branch before backtracking. A stack is last-in-first-out, so it naturally explores depth first; a queue is first-in-first-out, so it naturally explores breadth first. This single data-structure swap — stack vs. queue — is the entire difference between DFS and BFS.
In Python, the right tool for the queue is collections.deque, not a plain list. A list’s pop(0) is O(n) because every remaining element has to shift left one slot; a deque‘s popleft() is O(1) because it’s backed by a doubly linked block structure designed for cheap operations at both ends.
A common refinement is level tracking: instead of just visiting nodes in level order, you often want to know where one level ends and the next begins (to compute per-level sums, find the rightmost node of each level, or return a list of lists). The standard technique is to record len(queue) at the start of each iteration of the outer loop — that number is exactly how many nodes belong to the current level, because at that instant the queue contains only current-level nodes: all previous levels have already been popped, and no next-level nodes have been pushed yet.
Time and Space Complexity
Let n be the number of nodes in the tree.
| Operation | Time | Space | Why |
|---|---|---|---|
| Level-order traversal (visit all nodes) | O(n) |
O(n) worst case |
Every node is pushed onto the queue exactly once and popped exactly once, so total work is proportional to the node count. Space is dominated by the queue, which at its widest holds up to roughly half the nodes for a complete binary tree’s last level. |
| Per-level grouping (list of lists) | O(n) |
O(n) |
Same traversal, plus O(n) total space to store every value across all the output sublists. |
The time complexity is always O(n) — there’s no best/average/worst distinction the way there is for, say, binary search on a sorted array, because level-order traversal always visits every node exactly once regardless of the tree’s shape or the values stored in it. The space complexity, however, does depend on shape: for a completely skewed tree (every node has only one child, effectively a linked list), the queue never holds more than one node at a time, so auxiliary space beyond the output is O(1). For a wide, balanced tree, the widest level can hold roughly half the nodes, so the queue’s peak size is O(n). When people say “level-order traversal is O(n) space,” they mean the worst case over all tree shapes.
Examples
Example 1: Basic level-order traversal as a list of lists
from collections import deque
class TreeNode:
def __init__(self, val: int, left: "TreeNode | None" = None, right: "TreeNode | None" = None) -> None:
self.val = val
self.left = left
self.right = right
def level_order(root: "TreeNode | None") -> list[list[int]]:
if root is None:
return []
result: list[list[int]] = []
queue: deque[TreeNode] = deque([root])
while queue:
level_size = len(queue)
current_level: list[int] = []
for _ in range(level_size):
node = queue.popleft()
current_level.append(node.val)
if node.left is not None:
queue.append(node.left)
if node.right is not None:
queue.append(node.right)
result.append(current_level)
return result
# 1
# / \
# 2 3
# / \ \
# 4 5 6
root = TreeNode(1,
TreeNode(2, TreeNode(4), TreeNode(5)),
TreeNode(3, None, TreeNode(6)))
print(level_order(root))Output:
[[1], [2, 3], [4, 5, 6]]The queue starts as [1]. On the first outer-loop pass, level_size is 1, so exactly one node (1) is popped, its value collected into current_level, and its children 2 and 3 pushed. On the second pass, level_size is 2, so 2 and 3 are popped (pushing 4, 5, and 6), producing [2, 3]. On the third pass, level_size is 3, and 4, 5, 6 are popped with no children to push, producing [4, 5, 6]. The queue is now empty, so the loop ends.
Example 2: Right side view of a tree
A classic interview question — “what would you see standing to the right of the tree?” — is level-order traversal in disguise: for each level, you only keep the last node visited.
from collections import deque
class TreeNode:
def __init__(self, val: int, left: "TreeNode | None" = None, right: "TreeNode | None" = None) -> None:
self.val = val
self.left = left
self.right = right
def right_side_view(root: "TreeNode | None") -> list[int]:
if root is None:
return []
view: list[int] = []
queue: deque[TreeNode] = deque([root])
while queue:
level_size = len(queue)
for i in range(level_size):
node = queue.popleft()
if i == level_size - 1:
view.append(node.val)
if node.left is not None:
queue.append(node.left)
if node.right is not None:
queue.append(node.right)
return view
# 1
# / \
# 2 3
# \ \
# 5 6
# /
# 7
root = TreeNode(1,
TreeNode(2, None, TreeNode(5)),
TreeNode(3, None, TreeNode(6, TreeNode(7), None)))
print(right_side_view(root))Output:
[1, 3, 6, 7]Level 0 has only 1, so it’s automatically the last node and gets added. Level 1 is [2, 3] in pop order; 3 is popped last (i == level_size - 1), so 3 is added. Level 2 is [5, 6]; 6 is popped last, so 6 is added. Level 3 has only 7 (the left child of 6), so it’s added too. Notice that 5 (the right child of 2) never appears in the final view — it’s hidden behind 6 from the right side, exactly as the algorithm predicts.
Example 3: Average value at each level
from collections import deque
class TreeNode:
def __init__(self, val: int, left: "TreeNode | None" = None, right: "TreeNode | None" = None) -> None:
self.val = val
self.left = left
self.right = right
def average_of_levels(root: "TreeNode | None") -> list[float]:
if root is None:
return []
averages: list[float] = []
queue: deque[TreeNode] = deque([root])
while queue:
level_size = len(queue)
level_sum = 0
for _ in range(level_size):
node = queue.popleft()
level_sum += node.val
if node.left is not None:
queue.append(node.left)
if node.right is not None:
queue.append(node.right)
averages.append(level_sum / level_size)
return averages
# 3
# / \
# 9 20
# / \
# 15 7
root = TreeNode(3,
TreeNode(9),
TreeNode(20, TreeNode(15), TreeNode(7)))
print(average_of_levels(root))Output:
[3.0, 14.5, 11.0]Level 0 is just [3], average 3.0. Level 1 is [9, 20], sum 29, average 14.5. Level 2 is [15, 7], sum 22, average 11.0. Notice this reuses the exact same skeleton as Example 1 — level-order traversal is a template you adapt by changing what you do with each level’s nodes, not a different algorithm each time.
How it works step by step
Trace level_order from Example 1 on the tree rooted at 1 with children 2 and 3, where 2 has children 4 and 5, and 3 has a right child 6:
| Step | Queue before pop | Node popped | Pushed | current_level after step |
|---|---|---|---|---|
| 1 | [1] | 1 | 2, 3 | [1] |
| 2 | [2, 3] | 2 | 4, 5 | [2] |
| 3 | [3, 4, 5] | 3 | 6 | [2, 3] |
| 4 | [4, 5, 6] | 4 | (none) | [4] |
| 5 | [5, 6] | 5 | (none) | [4, 5] |
| 6 | [6] | 6 | (none) | [4, 5, 6] |
Step 1 is its own outer-loop pass (level_size was 1), producing result = [[1]]. Steps 2 and 3 together are the second outer-loop pass (level_size was 2, captured before either pop happened), producing result = [[1], [2, 3]]. Steps 4 through 6 are the third pass (level_size was 3), producing the final result = [[1], [2, 3], [4, 5, 6]]. The key invariant to notice: level_size is read once, before the inner loop starts, and never recomputed mid-level — that’s what keeps levels from bleeding into each other even though the queue is being pushed to and popped from at the same time.
Common Mistakes
Mistake 1: Iterating over the queue while mutating it
It’s tempting to loop directly over the queue with for node in queue instead of using range(level_size) with explicit popleft() calls. This fails because you’re appending to the same deque you’re iterating over:
def level_order_broken(root):
if root is None:
return []
result = []
queue = deque([root])
while queue:
current_level = []
for node in queue: # BUG: mutating queue while iterating it
current_level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
queue.popleft()
result.append(current_level)
return resultJust like a list, a deque raises RuntimeError: deque mutated during iteration the moment you append to or pop from it while a for loop is walking over it. The fix is what Example 1 does: snapshot level_size = len(queue) before the inner loop, then drive the loop with range(level_size) and explicit popleft() calls, so mutation and iteration never touch the same live view of the collection.
level_size = len(queue)
for _ in range(level_size):
node = queue.popleft()
current_level.append(node.val)
if node.left is not None:
queue.append(node.left)
if node.right is not None:
queue.append(node.right)Mistake 2: A mutable default argument in a recursive level-order helper
Level order is usually iterative, but it’s also possible (and sometimes asked in interviews) to build it with DFS-style recursion plus a level index. A classic Python trap shows up here as a mutable default argument:
def level_order_recursive(root, level=0, result=[]): # BUG: shared default list
if root is None:
return result
if level == len(result):
result.append([])
result[level].append(root.val)
level_order_recursive(root.left, level + 1, result)
level_order_recursive(root.right, level + 1, result)
return resultDefault argument values are evaluated once, when the function is defined, not on every call. So every call that doesn’t explicitly pass result shares the exact same list object. Call this function on one tree, then call it again on a second tree, and the second call’s output will still contain leftover values from the first call. The fix is the standard Python idiom: default to None and create a fresh list inside the function body.
def level_order_recursive(
root: "TreeNode | None",
level: int = 0,
result: "list[list[int]] | None" = None,
) -> list[list[int]]:
if result is None:
result = []
if root is None:
return result
if level == len(result):
result.append([])
result[level].append(root.val)
level_order_recursive(root.left, level + 1, result)
level_order_recursive(root.right, level + 1, result)
return resultBest Practices
- Use
collections.dequefor the queue, never a plainlist—list.pop(0)isO(n), which quietly turns anO(n)traversal intoO(n²). - Snapshot
level_size = len(queue)before the inner loop whenever you need per-level boundaries (level lists, level sums, right-side view); readinglen(queue)mid-loop after pushes have happened gives the wrong count. - Always check
is not None(or truthiness) before pushing a child — pushingNoneonto the queue will crash on the next iteration when you try to read.val,.left, or.rightoff it. - Reach for level order (BFS) when the problem talks about levels, “closest to the root,” shortest path in an unweighted tree, or serializing/printing a tree row by row.
- Reach for a depth-first traversal instead when the problem is about root-to-leaf paths or subtree properties, or when memory on a very wide tree is a concern — DFS’s stack depth is bounded by the tree’s height, while BFS’s queue can grow to the width of the widest level.
- Don’t try to implement BFS with plain recursion — recursion mirrors a stack (depth-first), not a queue, so any “recursive level order” still needs an explicit queue (or level index) threaded through the calls; it isn’t natural recursion the way DFS is.
Practice Exercises
- Write a function
max_width(root)that returns the size of the widest level in a binary tree (the maximum number of nodes at any single depth). Hint: this is a one-line addition to the level-order skeleton — track the largestlevel_sizeyou see. - Write
zigzag_level_order(root)that returns level-order traversal, but alternates direction each level: level 0 left-to-right, level 1 right-to-left, level 2 left-to-right, and so on. Hint: collect each level normally, then reverse every other list before appending it to the result. - Write
is_complete_tree(root)that returnsTrueif a binary tree is a complete binary tree (every level fully filled except possibly the last, which is filled left to right with no gaps). Hint: do a level-order traversal that also pushesNoneplaceholders for missing children; if you ever pop a non-Nonenode after having already seen aNone, the tree isn’t complete.
Summary
- Level-order traversal (BFS on a tree) visits nodes top to bottom, left to right, one full level at a time, using a FIFO queue instead of the stack that depth-first traversals use.
- In Python, back the queue with
collections.dequeand usepopleft()/append()— bothO(1)— rather than alist, whosepop(0)isO(n). - Time complexity is
O(n)for any tree shape, since every node is pushed and popped exactly once; space complexity isO(n)worst case (a wide, balanced tree) andO(1)best case beyond the output (a fully skewed tree). - To group output by level, snapshot
level_size = len(queue)before the inner loop — this is the pattern behind level lists, level averages, and right-side views. - Avoid iterating directly over the queue while mutating it (raises
RuntimeError), and avoid mutable default arguments (result=[]) in any recursive helper that accumulates results across calls. - Choose level order over depth-first traversal whenever the problem is naturally about levels, breadth, or shortest paths in an unweighted tree.
