Binary Tree Zigzag Level Order Traversal
Problem Statement
Given the root of a binary tree, return the zigzag level order traversal of its node values. The first level is read left-to-right, the next level right-to-left, and the direction alternates after every level.
Input
The root of a binary tree, such as [3,9,20,null,null,15,7].
Output
A list of lists where each level is included, but adjacent levels alternate their output direction.
Constraints
- •
0 <= number of nodes <= 2000 - •
-100 <= Node.val <= 100
Examples
Example 1
root = [3,9,20,null,null,15,7]
[[3],[20,9],[15,7]]Example 2
root = [1,2,3,4,null,null,5]
[[1],[3,2],[4,5]]Learning Objectives
- Reuse the fixed-size BFS level template from level order traversal.
- Separate traversal order from output order.
- Use a deque to build each level in the desired direction without reversing the whole tree traversal.
- Explain why children should still be enqueued left-to-right.
Intuition
Pattern Recognition
The signal is still do something per level, so the outer structure is the same BFS level sweep. The word zigzag changes only how each completed level is reported. It does not mean the queue should traverse the tree right-to-left on alternate levels.
The common trap is enqueuing children in different orders on different levels. That mutates the discovery order for later levels and can scramble grandchildren. Keep the queue boring and consistent: always enqueue left child before right child. Flip only the current level output, either by adding values to the front of a deque on right-to-left levels or by reversing odd levels after collection.
Common mistakes
- ×Alternating the child enqueue order instead of only alternating the output order.
- ×Forgetting to toggle the direction after every completed level.
- ×Reversing the entire answer instead of just the current odd-numbered level.
- ×Using repeated insertion at the front of an array list, which can add unnecessary shifting cost.
Algorithm Explanation
Key idea
The queue invariant is unchanged from normal level order: it holds the next level in left-to-right discovery order. For the output of the current level, use a deque. If the direction is left-to-right, append each value at the back. If the direction is right-to-left, insert each value at the front. Children are always enqueued left child then right child.
Level-by-level walkthrough
Use [3,9,20,null,null,15,7]. Start with queue [3] and direction left-to-right. Process 3, add it to the back of the level deque, and enqueue 9 then 20. The first output level is [3], and the next queue is [9,20].
Now the direction is right-to-left. The queue is still [9,20], so poll 9 before 20. Add 9 to the front of the level deque, then add 20 to the front, producing [20,9]. While doing that, enqueue 15 then 7 from node 20. The next queue is [15,7].
Toggle back to left-to-right. Process 15 then 7, add both to the back, and get [15,7]. The final answer is [[3],[20,9],[15,7]].
Algorithm
- Return an empty answer when root is null.
- Add root to the queue and set leftToRight to true.
- For each level, save levelSize = queue.size() and create an empty deque for that level values.
- Poll exactly levelSize nodes from the queue.
- If leftToRight is true, add the value to the back of the deque; otherwise add it to the front.
- Enqueue each node left child then right child when present.
- Convert the deque to a list, append it to the answer, and toggle leftToRight.
Solutions
Solution: Queue BFS with deque level output
Use this when you want to avoid reversing level lists. The queue still follows standard BFS, and the deque controls only the presentation of each level.
Run the normal fixed-level BFS. For each level, store values in a deque: add to the back on left-to-right levels and to the front on right-to-left levels. Always enqueue children left-to-right.
Step-by-step
- Return an empty list when root is null.
- Start a queue with root and a boolean direction flag set to left-to-right.
- For the current level, snapshot queue.size() and create a deque.
- Poll exactly that many nodes; place each value at the back or front of the deque based on the flag.
- Enqueue left child then right child for every node.
- Append the deque values as one list and flip the direction flag.
O(n)
O(width)
Each node is processed once, and the queue plus current level deque are bounded by the maximum tree width.
Java implementation
Dry Run
Sample input
root = [3,9,20,null,null,15,7]. The queue always discovers nodes left-to-right; only the level output changes direction.
| level | queue before level | direction | level output | result so far |
|---|---|---|---|---|
| 0 | [3] | left-to-right | [3] | [[3]] |
| 1 | [9,20] | right-to-left | [20,9] | [[3],[20,9]] |
| 2 | [15,7] | left-to-right | [15,7] | [[3],[20,9],[15,7]] |
Notice that the second row still polls 9 before 20. The output becomes [20,9] only because values are inserted at the front of the level deque.
Interview Tips
Be explicit that zigzag changes the output direction, not the child enqueue order. Interviewers often look for this distinction because alternating enqueue order can accidentally affect the next level rather than only the current one.
Likely follow-ups
- How would you implement the same idea by reversing odd levels after collection?
- How would you print the zigzag traversal as one flat list instead of grouped levels?
- How would this adapt to an n-ary tree?
- Can you do a spiral traversal without storing every level in the final answer?
Similar Problems
Key Takeaways
- Zigzag traversal is ordinary BFS plus alternating level presentation.
- The queue should still enqueue children left-to-right.
- A deque lets you build reversed levels without a separate reverse pass.
- Toggle the direction once per completed level, not once per node.