We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Binary Tree Zigzag Level Order Traversal

Difficulty: Medium

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, then right to left for the next level and alternate between).

Key Insights

  • The traversal should alternate directions at each level of the tree.
  • Breadth-First Search (BFS) can be employed to visit nodes level by level.
  • A deque can facilitate the zigzag behavior, allowing efficient appending on both ends.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the tree, since we visit each node exactly once. Space Complexity: O(m), where m is the maximum number of nodes at any level (the width of the tree), which could also be O(n) in the worst case.

Solution

To solve the problem, we will use a breadth-first search (BFS) approach, utilizing a queue to hold nodes at each level. We will use a deque to allow for efficient insertion of values based on the current level's direction (left to right or right to left). As we traverse each level, we will toggle the direction for the next level's traversal.

Code Solutions

from collections import deque

def zigzagLevelOrder(root):
    if not root:
        return []
    
    result = []
    queue = deque([root])
    left_to_right = True
    
    while queue:
        level_size = len(queue)
        level_values = deque()  # Use deque to facilitate zigzag insertion
        
        for _ in range(level_size):
            node = queue.popleft()
            if left_to_right:
                level_values.append(node.val)  # Append to the right
            else:
                level_values.appendleft(node.val)  # Append to the left
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(list(level_values))
        left_to_right = not left_to_right  # Toggle the direction
    
    return result
← Back to All Questions