Implementing Level-Order with Queue
What you'll learn: How to use a queue data structure to perform level-order (breadth-first) traversal of a binary tree systematically.
The Core Idea
Level-order traversal visits nodes level by level, from top to bottom and left to right. A queue is the perfect tool for this because it enforces the "first in, first out" (FIFO) order we need: nodes discovered first are processed first, and their children join the back of the line.
The algorithm:
- Start by enqueuing the root node
- While the queue isn't empty:
- Dequeue a node and process it (visit/print it)
- Enqueue its left child (if it exists)
- Enqueue its right child (if it exists)
- Repeat until the queue is empty
Why a Queue Works
Think of it like a factory assembly line: the root goes in first, gets processed, and its children join the end of the line. When the left child reaches the front, it gets processed and its children join the end. This naturally ensures we finish an entire level before moving to the next.
Simple Example
def level_order(root):
if root is None:
return
queue = [] # Using list as queue
queue.append(root) # Enqueue root
while queue:
node = queue.pop(0) # Dequeue front
print(node.value) # Process node
if node.left:
queue.append(node.left) # Enqueue left child
if node.right:
queue.append(node.right) # Enqueue right child
The queue temporarily holds nodes waiting to be visited, ensuring the correct breadth-first order automatically.
Key Takeaway: Level-order traversal uses a queue to process nodes level by level—enqueue the root, then repeatedly dequeue a node, process it, and enqueue its children until the queue is empty.