Learn how to perform a level-order (BFS) traversal on a binary tree using Python’s collections.deque
. This beginner-friendly guide shows you step-by-step code, intuition, and real examples, perfect for LeetCode prep!
Why Level-Order Traversal?
If Depth-First Search (DFS) is like diving deep down one path of a maze, Breadth-First Search (BFS) is like exploring each floor of a building one level at a time. In a binary tree, BFS lets us visit all nodes at depth 0 (the root), then depth 1 (its children), then depth 2, and so on.
Level-order traversal (BFS) is the go-to technique for:
- Finding the shortest path in unweighted graphs or trees.
- Printing a tree level by level (nice for debugging!).
- Solving problems like “Zigzag Level Order” or “Average of Levels” on LeetCode.
We’ll use Python’s collections.deque
as our queue (fast appends/pops) and build a result
list of lists, one sublist per level.
Also read about the Python Program to Find Maximum Depth of a Binary Tree.
Intuition & Approach
- Start at the root.
- Use a queue to hold nodes of the current level.
- While the queue isn’t empty:
- Note the current queue size (
level_size
), that’s how many nodes are on this level. - Dequeue each node, record its value.
- Enqueue its children (left then right) for the next level.
- After processing
level_size
nodes, you’ve finished one level—append the collected values toresult
.
- Note the current queue size (
This approach ensures we visit nodes in perfect left-to-right, level-by-level order.
Code Implementation
from collections import deque
def level_order_traversal(root):
"""
Perform a BFS (level-order) traversal on a binary tree and
return a list of levels, where each level is a list of node values.
"""
result = []
if not root:
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
Code Explanation
- Initialize:
result = []
will hold our final list of levels.- If
root
isNone
, return[]
immediately.
- Setup Queue:
queue = deque([root])
seeds the BFS with the root node.
- Main Loop:
- While
queue
has nodes, notelevel_size = len(queue)
. - Create an empty
current_level = []
to collect this level’s values.
- While
- Process One Level:
- Loop
level_size
times:node = queue.popleft()
dequeues the next node.current_level.append(node.val)
records its value.- If
node.left
exists,queue.append(node.left)
. - If
node.right
exists,queue.append(node.right)
.
- Loop
- Save Level:
- After the for-loop,
current_level
holds all values for one depth—append it toresult
.
- After the for-loop,
- Continue:
- The next iteration processes the next depth, until the queue is empty.
Dry Run (Example)
Given the tree:
1
/ \
2 3
/ \ \
4 5 6
- Start:
queue = [1]
- Level 0:
level_size = 1
.- Dequeue
1
→current_level = [1]
. - Enqueue
2, 3
. - Append
[1]
toresult
.
- Level 1:
queue = [2, 3]
,level_size = 2
.- Dequeue
2
→[2]
, enqueue4,5
. - Dequeue
3
→[2,3]
, enqueue6
. - Append
[2,3]
.
- Level 2:
queue = [4,5,6]
,level_size = 3
.- Dequeue
4
→[4]
. No children. - Dequeue
5
→[4,5]
. No children. - Dequeue
6
→[4,5,6]
. No children. - Append
[4,5,6]
.
- Done:
queue
empty.
Final result
: [[1], [2,3], [4,5,6]]
Time and Space Complexity
- Time Complexity:
- We visit each of the
N
nodes exactly once → O(N).
- We visit each of the
- Space Complexity:
- The queue may hold up to the entire width of the tree (worst case,
N/2
nodes at the lowest level) → O(N). - The
result
list stores all values → O(N).
- The queue may hold up to the entire width of the tree (worst case,
Conclusion
Level-order traversal via BFS is incredibly powerful for problems that need to process nodes by depth. Python’s deque
keeps it elegant and efficient. Whether you’re printing a tree level by level, finding the shortest path, or prepping for LeetCode’s “Binary Tree Zigzag” question, mastering this pattern is a must-have in your toolkit.
For any changes to the document, kindly email at code@codeanddebug.in or contact us at +91-9712928220.