Implementing Binary Tree Level Order Traversal

Problem Description
Binary tree level order traversal (also known as breadth-first traversal) requires visiting the nodes of a binary tree in hierarchical order, starting from the root node and accessing each node level by level from left to right. This is one of the most fundamental and important algorithms for binary tree traversal.

Solution Approach
The core idea of level order traversal is to use a queue (a FIFO structure) to maintain the order of nodes to be visited:

1. Enqueue the root node.
2. Repeat the following steps until the queue is empty:
   • Dequeue a node and visit it.
   • Enqueue the node's left child (if it exists).
   • Enqueue the node's right child (if it exists).

Detailed Step-by-Step Breakdown

1. Basic Level Order Traversal (Returns a one-dimensional array)

def levelOrder(root):
    if not root:
        return []
    
    result = []
    queue = collections.deque([root])  # Initialize the queue
    
    while queue:
        node = queue.popleft()  # Dequeue
        result.append(node.val)  # Visit the node value
        
        # Enqueue child nodes
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    
    return result

2. Level Order Traversal with Level Separation (Returns a two-dimensional array)

def levelOrder(root):
    if not root:
        return []
    
    result = []
    queue = collections.deque([root])
    
    while queue:
        level_size = len(queue)  # Number of nodes in the current level
        level_nodes = []  # Store node values for the current level
        
        for _ in range(level_size):
            node = queue.popleft()
            level_nodes.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(level_nodes)  # Add the current level to the result
    
    return result

3. Zigzag Level Order Traversal (Sawtooth traversal)

def zigzagLevelOrder(root):
    if not root:
        return []
    
    result = []
    queue = collections.deque([root])
    left_to_right = True  # Traversal direction flag
    
    while queue:
        level_size = len(queue)
        level_nodes = [0] * level_size  # Pre-allocate space
        
        for i in range(level_size):
            node = queue.popleft()
            
            # Determine insertion position based on direction
            index = i if left_to_right else level_size - 1 - i
            level_nodes[index] = node.val
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(level_nodes)
        left_to_right = not left_to_right  # Reverse direction
    
    return result

Complexity Analysis

• Time Complexity: O(n), each node is visited exactly once.
• Space Complexity: O(n), the queue stores at most n nodes.

Key Points

1. Queue Selection: Using a double-ended queue (deque) is more efficient than a list.
2. Level Separation Technique: Record the current queue length before starting the loop to distinguish between different levels.
3. Edge Case Handling: Special cases like empty trees need to be handled separately.
4. Direction Control: Zigzag traversal is implemented via index calculation, avoiding repeated list reversals.

Practical Application Scenarios

• Calculating the minimum depth of a binary tree.
• Right view / Left view of a binary tree.
• Determining if a tree is a complete binary tree.
• Designing optimal strategies for constructing binary trees.