MediumNeetCode150TreeBreadth-First SearchBinary Tree
Binary Tree Zigzag Level Order Traversal
Zigzag level order traversal.
Examples
Input
root = [3,9,20,null,null,15,7]
Output
[[3],[20,9],[15,7]]
Alternating left-to-right and right-to-left.
Constraints
- •
Number of nodes in [0,2000] - •
-1000 <= Node.val <= 1000
Approaches
Level order, reverse odd levels.
CodeT: O(n) | S: O(n) queue
Use deque for zigzag.
CodeT: O(n) | S: O(n) deque
Same approach.
CodeT: O(n) | S: O(n)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| BFS + Reverse | O(n) | O(n) queue | Level order, reverse odd levels. |
| BFS Deque | O(n) | O(n) deque | Use deque for zigzag. |
| BFS Optimized | O(n) | O(n) | Same approach. |
BFS + Reverse
T: O(n)S: O(n) queue
Level order, reverse odd levels.
BFS Deque
T: O(n)S: O(n) deque
Use deque for zigzag.
BFS Optimized
T: O(n)S: O(n)
Same approach.
Common Mistakes
Not handling null root
Wrong zigzag direction
Off-by-one in level