Level Order Traversal (BFS)
DSA · Trees
Theory
Level-order traversal visits nodes level by level from left to right using a queue. Start with the root in the queue; repeatedly remove a node, record it, and add its children. Processing the queue size at the start of each round groups nodes by level. It runs in O(n) time and uses O(w) space for the widest level w.
Why we use it
It reveals the tree level by level, which is needed for shortest-path style questions in trees.
When to use it
Use it to print levels, find the minimum depth, get the right-side view, connect nodes on the same level, or serialise trees level by level.
How it works
- queue = [root]
- Queue empty? Yes: Done. No: Pop front node, visit it.
- Push its left and right children
- Repeat level by level
Syntax
queue = deque([root])
while queue:
for _ in range(len(queue)):
node = queue.popleft(); visit(node)
add node.left, node.right if presentExample
from collections import deque
class Node:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
root = Node(3, Node(9), Node(20, Node(15), Node(7)))
def level_order(root):
levels, q = [], deque([root])
while q:
level = []
for _ in range(len(q)):
n = q.popleft()
level.append(n.val)
if n.left: q.append(n.left)
if n.right: q.append(n.right)
levels.append(level)
return levels
levels = level_order(root)
print("Levels:", levels)
print("Right side view:", [lvl[-1] for lvl in levels])Key points
- Uses a queue, not recursion
- Visits nodes level by level
- Queue size per round groups levels
- O(n) time, O(width) space