← Back to DSA Animator
Binary Tree Zigzag Level Order Traversal LC #103 Medium BFS · Direction Flag
Problem

Given the root of a binary tree, return the zigzag level order traversal of its nodes' values (i.e., from left to right, then right to left for the next level, alternating).

Example 1
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]
Explanation: L1 left→right: [3]. L2 right←left: [20,9]. L3 left→right: [15,7].
Example 2
Input: root = [1,2,3,4,5]
Output: [[1],[3,2],[4,5]]
Example 3
Input: root = [1]
Output: [[1]]
Constraints: 0 ≤ nodes ≤ 2000  |  −100 ≤ Node.val ≤ 100
Try Examples
Custom:
Approach
BFS with Direction Flag Toggle
Enqueue children left→right always. But insert polled values: addLast for L→R levels, addFirst for R←L levels. Toggle the flag after each level.
Direction Indicator
Current Traversal Direction
Left → Right
L1: addLast(val)
addLast(val)
Binary Tree
Level 1
Level 2
Level 3
Level 4+
In Queue
Processing
BFS Queue
Queue is empty
Zigzag Output Levels
No levels collected yet…
Variables
Level #
—
direction
L→R
sz (snapshot)
—
result.size
0
Method Call Trace
Step Logic
Press ▶ Play or Next Step to begin the animation.
🎉
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
Offer root to queue; init leftToRight = true
2
Snapshot sz = queue.size(); create LinkedList<Integer> level
3
Poll node: addLast(val) if L→R, addFirst(val) if R←L; enqueue children left→right
4
Add completed level to result; flip leftToRight = !leftToRight
Time
O(n)
Space
O(n)
Why the Direction Flag Works

Children are always enqueued left→right, so the queue order never changes. The trick is how we insert into the level list. For L→R levels we call addLast(val) — values accumulate in natural order. For R←L levels we call addFirst(val) — each new value is prepended, reversing the order without any extra reversal pass. After every level we flip leftToRight = !leftToRight. One boolean, zero extra work — O(1) per node.