Domain 2MediumCORE

Binary Tree Zigzag Level Order Traversal

We are given the root of a binary tree and need to return its level-order traversal, but with a specific twist. Instead of printing every level from left-to-right (standard BFS), we must alternate directions: Level 0 is Left-to-Right, Level 1 is Right-to-Left, Level 2 is Left-to-Right again, and so on.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Stack#Tree#Breadth-first Search

103. Binary Tree Zigzag Level Order Traversal

Model: qwen3.5:9b
Topics: Stack,Tree,Breadth-first Search
FAANG asked: 1
Acceptance rate: 50.4%


Problem Breakdown

We are given the root of a binary tree and need to return its level-order traversal, but with a specific twist. Instead of printing every level from left-to-right (standard BFS), we must alternate directions: Level 0 is Left-to-Right, Level 1 is Right-to-Left, Level 2 is Left-to-Right again, and so on.

Inputs: A binary tree node (root) defined by a standard TreeNode structure with integer values. Outputs: A list of lists (list of levels), where each inner list contains the integers for that level in the specific zigzag order described above. Constraints & Edge Cases:

  • The tree can be empty (None). If so, return an empty list immediately.
  • Node values range from -100 to 100 (integers). No overflow issues expected with standard integer types.
  • Tree depth is up to the number of nodes (2000), implying we must handle recursion or iteration carefully; BFS is preferred here over DFS for level control.

Intuition

A naive approach might be a Depth First Search (DFS) where we track levels in an array and reverse specific subarrays at the end, but that requires careful state management to ensure we don’t overwrite previous levels’ data incorrectly during recursion.

The most natural way to process “level by level” is Breadth-First Search (BFS). In a standard BFS using a queue:

  1. We pop all nodes currently in the queue for one iteration of our outer loop, which represents exactly one tree level.
  2. This naturally gives us the values from left-to-right as we process them.

The key insight is that the physical order of traversal (popping children) remains standard BFS (Left child first, then Right child). The “zigzag” requirement only affects how we record or output these nodes for specific levels. Therefore, instead of changing our queue insertion logic—which would complicate future level processing—we simply collect each level’s values into a temporary list and reverse that list if the current level index is odd (1st level in 0-indexed terms).

Approach

We will use collections.deque for an efficient O(1) pop from the left.

  1. Initialization: Check if root is empty; return []. Initialize a queue with [root], initialize result list, and track current level index (starting at 0).
  2. Level Loop: While the queue has nodes:
    • Determine how many nodes are currently in the queue (level_size). This defines the scope of our inner loop for this specific tree depth.
    • Create a current_level list to store values popped from the queue during this iteration.
    • Iterate level_size times: pop node, append its value to current_level, and enqueue its left/right children (if they exist). Note that we always push Left then Right into the queue regardless of zigzag direction; this maintains standard BFS order for subsequent levels.
  3. Direction Toggle: After collecting all nodes for a level, check if the current level index is odd (level % 2 == 1). If so, reverse current_level before appending to our result list. Increment level counter and continue until queue empty.

Complexity Analysis

  • Time Complexity: O(N), where N is the number of nodes in the tree. We visit every node exactly once (enqueue/dequeue operations are constant time). Reversing a sublist takes proportional time to its length, but across all levels, we touch each element’s value at most twice (once collected, potentially reversed), summing up linearly with respect to N total elements.
  • Space Complexity: O(W), where W is the maximum width of the tree (maximum number of nodes in any level). This accounts for the queue storage and the temporary current_level list used during traversal. The output result itself takes O(N) space, but that is typically excluded from auxiliary complexity analysis unless specified otherwise.

Solution

from collections import deque
from typing import List, Optional

# 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: Optional[TreeNode]) -> List[List[int]]:
    if not root:
        return []
    
    queue = deque([root])
    result = []
    level_idx = 0
    
    while queue:
        # Number of nodes at the current depth level
        level_size = len(queue)
        current_level_nodes = []
        
        for _ in range(level_size):
            node = queue.popleft()
            current_level_nodes.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
                
        # If odd level index, reverse the collected values (Right-to-Left order)
        if level_idx % 2 == 1:
            current_level_nodes.reverse()
            
        result.append(current_level_nodes)
        
        # Move to next level
        level_idx += 1
        
    return result

Edge Cases Handled

  • Empty Tree: The function checks if not root immediately and returns an empty list.
  • Single Node: The loop runs once, processes the single node, appends [val], queue becomes empty, terminates correctly.
  • Skewed Trees (Left/Right Heavy): Standard BFS handles depth naturally; zigzag logic applies per level regardless of tree shape.
  • Negative Values: node.val is appended directly to lists without type checking or transformation, preserving the integer value as required by constraints (-100 <= val <= 100).