Breadth-First Search
Level-order traversal using queues. Learn when BFS is preferred over DFS for tree problems.
Breadth-First Search (BFS) on trees explores level by level, visiting all nodes at depth d before moving to depth d+1. This is also called level-order traversal.
How BFS Works
BFS uses a queue to process nodes level by level:
- Start with root in queue
- While queue is not empty:
- Dequeue a node
- Process it
- Enqueue its children
1
/ \
2 3
/ \ \
4 5 6
BFS Order: 1, 2, 3, 4, 5, 6
Level 0: 1
Level 1: 2, 3
Level 2: 4, 5, 6
Basic Implementation
from collections import deque
def bfs(root):
if root is None:
return
queue = deque([root])
while queue:
node = queue.popleft()
print(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
Level-Order Traversal with Levels
Often we need to know which level each node is on:
def level_order(root):
if root is None:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue)
current_level = []
for _ in range(level_size):
node = queue.popleft()
current_level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(current_level)
return result
3
/ \
9 20
/ \
15 7
Output: [[3], [9, 20], [15, 7]]
Tracking Levels
The key insight is processing all nodes at the current level before moving to the next. We do this by recording the queue size at the start of each level and processing exactly that many nodes.
Reverse Level Order
Process levels from bottom to top:
def level_order_bottom(root):
if root is None:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue)
current_level = []
for _ in range(level_size):
node = queue.popleft()
current_level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(current_level)
return result[::-1] # Reverse
Zigzag Level Order
Alternate direction at each level:
def zigzag_level_order(root):
if root is None:
return []
result = []
queue = deque([root])
left_to_right = True
while queue:
level_size = len(queue)
current_level = []
for _ in range(level_size):
node = queue.popleft()
current_level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
if not left_to_right:
current_level.reverse()
result.append(current_level)
left_to_right = not left_to_right
return result
Right Side View
See the tree from the right side:
def right_side_view(root):
if root is None:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue)
for i in range(level_size):
node = queue.popleft()
# Last node in this level is visible from right
if i == level_size - 1:
result.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
1
/ \
2 3
/ \
4 5
Right side view: [1, 3, 5]
Level Averages
Calculate average value at each level:
def average_of_levels(root):
if root is None:
return []
result = []
queue = 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:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level_sum / level_size)
return result
Maximum Depth (BFS)
def max_depth(root):
if root is None:
return 0
depth = 0
queue = deque([root])
while queue:
level_size = len(queue)
depth += 1
for _ in range(level_size):
node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return depth
Minimum Depth (Shortest Path to Leaf)
BFS naturally finds the shortest path:
def min_depth(root):
if root is None:
return 0
queue = deque([root])
depth = 1
while queue:
level_size = len(queue)
for _ in range(level_size):
node = queue.popleft()
# Check if it's a leaf
if node.left is None and node.right is None:
return depth
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
depth += 1
return depth
BFS for Shortest Path
BFS guarantees finding the shortest path (in terms of edges) because it explores all nodes at distance d before any node at distance d+1. This is why min_depth uses BFS.
Connect Next Pointers
Connect each node to its right neighbor at the same level:
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.next = None # Points to right neighbor
def connect(root):
if root is None:
return root
queue = deque([root])
while queue:
level_size = len(queue)
prev = None
for _ in range(level_size):
node = queue.popleft()
if prev:
prev.next = node
prev = node
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return root
BFS vs DFS
| Aspect | BFS | DFS | |--------|-----|-----| | Order | Level by level | Branch by branch | | Data structure | Queue | Stack (or recursion) | | Space | O(max width) | O(height) | | Shortest path | Yes (in edges) | No | | Memory for wide trees | Higher | Lower | | Memory for deep trees | Lower | Higher |
Use BFS when:
- Finding shortest path
- Level-order operations
- Trees are very deep but not wide
Use DFS when:
- Exploring all paths
- Trees are very wide but not deep
- Need to backtrack
Complete vs Perfect Tree Properties
For a complete binary tree with n nodes:
- Maximum width: ⌈n/2⌉ at the last level
- Height: ⌊log₂n⌋
Perfect tree with 15 nodes:
1
/ \
2 3
/ \ / \
4 5 6 7
/\ /\ /\ /\
8 9... ...15
Width at last level: 8
Height: 3
Time and Space Complexity
- Time: O(n) - visit each node once
- Space: O(w) where w is maximum width
- Worst case (complete tree): O(n/2) = O(n)
- Best case (skewed tree): O(1)
Key Takeaways
- BFS visits nodes level by level using a queue
- Track level boundaries by recording queue size
- BFS finds shortest path (in edges) naturally
- Space complexity depends on tree width, not height
- Ideal for level-specific operations and shortest paths
- Can be modified for zigzag, reverse, and side views
Level-order traversal is essential for problems that require processing nodes by depth. Understanding when BFS is preferred over DFS—particularly for shortest path problems—is key to choosing the right approach.