[Intermediate] — visiting a tree one depth at a time, and the queue that makes it work.

Before you start

After this lesson you will be able to:

  1. Perform a level-order traversal by hand, and implement it with a queue.
  2. Produce output grouped by level, not just a flat sequence.
  3. Say when level-order is the right choice and when depth-first is.
  4. Explain why this traversal uses a queue where the others use a stack.

Study route: read the mechanism, then the grouped-by-level variant, then the comparison at the end.


5. Breadth-First Traversal (Level-Order Traversal)

Unlike DFS traversals, Level-Order Traversal visits nodes level by level from top to bottom, left to right.

Because recursion uses a LIFO call stack, Level-Order cannot be written recursively. It uses an explicit Queue (FIFO) data structure:

from collections import deque
 
def level_order(root: TreeNode) -> list:
    """Level-order traversal using an explicit Queue."""
    if root is None:
        return []
    
    result = []
    queue = deque([root])  # Initialize FIFO Queue with root
    
    while queue:
        current = queue.popleft()  # Remove next node from queue
        result.append(current.val)
        
        # Enqueue left child if it exists
        if current.left:
            queue.append(current.left)
            
        # Enqueue right child if it exists
        if current.right:
            queue.append(current.right)
            
    return result
 
# Visited Order: [1, 2, 3, 4, 5]

6. Time & Space Complexity Summary

Traversal TypeTime ComplexitySpace Complexity (Auxiliary Stack/Queue)
Preorder (DFS) call stack space ().
Inorder (DFS) call stack space ( balanced, degenerate).
Postorder (DFS) call stack space.
Level-Order (BFS) queue space (, up to leaves).

7. Common Pitfalls & Traps

  1. Stack Overflow on Deep Trees: Recursive DFS uses the CPU call stack. For a degenerate tree of height , recursive traversal causes a RecursionError / Stack Overflow. Use an explicit iterative stack for deep trees.
  2. Queue vs Stack Trap in BFS: Level-order requires a FIFO Queue (popleft()). Accidental use of a LIFO Stack (pop()) turns BFS into a bizarre right-to-left DFS traversal!
  3. Inorder Fallacy: Inorder traversal only produces sorted output on Binary Search Trees (BSTs). On arbitrary binary trees, it does not guarantee sorted order.

Before moving on

You can implement level-order traversal, group its output by level, and say when to prefer it.

Recap: level-order visits every node at one depth before moving deeper, using a queue rather than a stack; it costs time and space where is the widest level — which for a perfect tree is about , so it can use far more memory than a depth-first traversal on the same tree; it is the right choice when the answer depends on depth, such as finding the shallowest node satisfying something, or printing a tree level by level.

↑ Back to Traversal