Visualizer › Trees
Level Order Traversal (BFS)
Visits the tree level by level, left to right, using a queue — breadth-first search on a tree.
How it works
- Space is the widest level w.
- Process the queue size at a time to separate levels.
- Basis for right view, zigzag and minimum depth problems.
Complexity
- Best time: O(n)
- Average time: O(n)
- Worst time: O(n)
- Extra space: O(w)
Code (Python)
from collections import deque
def level_order(root):
out, q = [], deque([root] if root else [])
while q:
node = q.popleft()
out.append(node.val)
if node.left: q.append(node.left)
if node.right: q.append(node.right)
return outPractise: Trees problems