Course contentsShow
← Computer Science
Lesson 479 of 2,87211. Binary TreesFree lesson

Implementing Level-Order with Queue

Using a queue to track nodes at each level: enqueue root, dequeue and process, enqueue children, repeat.

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:

  1. Start by enqueuing the root node
  2. 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)
  3. 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.