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:
- We pop all nodes currently in the queue for one iteration of our outer loop, which represents exactly one tree level.
- 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.
- Initialization: Check if root is empty; return
[]. Initialize a queue with[root], initialize result list, and track current level index (starting at 0). - 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_levellist to store values popped from the queue during this iteration. - Iterate
level_sizetimes: pop node, append its value tocurrent_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.
- Determine how many nodes are currently in the queue (
- Direction Toggle: After collecting all nodes for a level, check if the current level index is odd (
level % 2 == 1). If so, reversecurrent_levelbefore 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_levellist 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 rootimmediately 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.valis appended directly to lists without type checking or transformation, preserving the integer value as required by constraints (-100 <= val <= 100).