DSA problem
Binary Tree Zigzag Level Order Traversal
Given the root of a binary tree, return the zigzag level order traversal of its nodes' values: the first level is left to right, the second level is right to left, and the direction continues to alternate between levels.
This problem is a small twist on the classic level-order traversal. The structural BFS is identical — we still process the tree level by level using a queue — but the ordering of values within each level must flip between left-to-right and right-to-left as the depth increases.
There are two clean ways to implement the flip. The simplest is to always enqueue children in their natural left-to-right order, collect the level's values into a list, and reverse that list whenever the level index is odd. This costs O(level_size) per reversal but is easy to reason about and to test.
A second approach uses a deque for the per-level container: when the level is left-to-right we push to the back; when it is right-to-left we push to the front. Both approaches run in O(n) total time and O(w) extra space, where w is the maximum width of the tree. We present the deque-based version below because it avoids a separate reverse pass.
Examples
root = [3,9,20,null,null,15,7][[3],[20,9],[15,7]]root = [1][[1]]root = [][]Constraints
- The number of nodes in the tree is in the range [0, 2000].
- -100 <= Node.val <= 100
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.