LeetCode Solutions Blog

Binary Tree Zigzag Level Order Traversal

Number: 103

Difficulty: Medium

Paid? No

Problem Description

Given the root of a binary tree, return the zigzag level order traversal of its nodes' values (i.e., from left to right on one level and then right to left on the next, alternating between).

Key Insights

Use a breadth-first search (BFS) approach to traverse the tree level by level.
Alternate the direction of traversal on each level to achieve the zigzag pattern.
A flag or counter can be used to determine the order of nodes for the current level.
Using a double-ended data structure or simply reversing the list at every alternate level is an effective approach.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes, because each node is visited exactly once. Space Complexity: O(n), as in the worst-case scenario (e.g., a complete binary tree) the queue used for BFS may hold O(n) nodes at once.

Solution

We can solve this problem using a breadth-first search (BFS). Start by initializing a queue to hold nodes for each level. For each level:

Determine the number of nodes at the current level.
Iterate over these nodes, appending their children for the next level.
Depending on a flag (or level count), either append node values in the natural order (left to right) or reverse the order (right to left) before adding to the result. Key data structures:

A queue for BFS traversal.
A list (or similar container) to store current level values. The main trick is toggling the order of insertion or reversing the list at alternate levels to achieve the "zigzag" pattern.

Code Solutions

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

def zigzagLevelOrder(root):
    # If the tree is empty, return an empty list
    if not root:
        return []
    
    # Initialize the result list and the queue with the root node.
    result = []
    queue = [root]
    left_to_right = True  # Flag to indicate the current direction of traversal
    
    # Process the tree level by level.
    while queue:
        level_size = len(queue)
        current_level = []
        
        # Process all nodes for the current level.
        for i in range(level_size):
            node = queue.pop(0)  # Dequeue the node from the front of the queue
            current_level.append(node.val)  # Append the node's value
            
            # Enqueue the left child if it exists.
            if node.left:
                queue.append(node.left)
            # Enqueue the right child if it exists.
            if node.right:
                queue.append(node.right)
        
        # If the current level's order is right-to-left, reverse the list.
        if not left_to_right:
            current_level.reverse()
        
        # Append the current level's values to the result.
        result.append(current_level)
        # Toggle the direction for the next level.
        left_to_right = not left_to_right
    
    return result