Binary Tree Zigzag Level Order Traversal medium

Problem Statement

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

Example 1:

Input: root = [3,9,20,null,null,15,7] Output: [[3],[20,9],[15,7]]

Example 2:

Input: root = [1] Output: [[1]]

Steps

1. Initialization: Create an empty list result to store the zigzag traversal. Create a queue q to perform a breadth-first search (BFS). Initialize a variable left_to_right to True to indicate the traversal direction.

2. BFS Traversal:

   • Enqueue the root node into the q.
   • While the queue is not empty:
     • Get the current level size (level_size). This represents the number of nodes at the current level.
     • Create an empty list level_nodes to store the nodes' values at the current level.
     • Iterate level_size times:
       • Dequeue a node from the q.
       • If left_to_right is True, append the node's value to the level_nodes list. Otherwise, prepend the node's value to the level_nodes list.
       • Enqueue the node's left and right children (if they exist).
     • Append the level_nodes list to the result list.
     • Toggle left_to_right to change the traversal direction for the next level.

3. Return Result: Return the result list.

Explanation

The algorithm uses a breadth-first search (BFS) to traverse the binary tree level by level. The key is toggling the left_to_right flag to alternate between appending (left-to-right) and prepending (right-to-left) the nodes' values to the level_nodes list. This ensures the zigzag pattern. Prepending is efficiently done using level_nodes.insert(0, node.val).

Code

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def zigzagLevelOrder(root):
    if not root:
        return []

    result = []
    q = deque([root])
    left_to_right = True

    while q:
        level_size = len(q)
        level_nodes = []
        for _ in range(level_size):
            node = q.popleft()
            if left_to_right:
                level_nodes.append(node.val)
            else:
                level_nodes.insert(0, node.val)  #Prepend for right-to-left

            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)

        result.append(level_nodes)
        left_to_right = not left_to_right  # Toggle direction

    return result

# Example Usage
root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
print(zigzagLevelOrder(root))  # Output: [[3], [20, 9], [15, 7]]

root = TreeNode(1)
print(zigzagLevelOrder(root)) # Output: [[1]]

Complexity

• Time Complexity: O(N), where N is the number of nodes in the binary tree. We visit each node exactly once.
• Space Complexity: O(W), where W is the maximum width of the binary tree. In the worst case (a complete binary tree), W can be proportional to N, resulting in O(N) space complexity. This is due to the queue used in BFS.