DSA AnimatorDSA animations
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.

How to solve Binary Tree Zigzag Level Order Traversal

LeetCode 103 · Medium · Tree · Pattern: BFS Level Order

Why the obvious approach is slow

One way is to run a normal level order traversal, and then reverse every second level at the end. That is fine, but it touches some levels twice. We can place each value in its correct slot directly.

The key idea

Run a normal breadth first search, one level per round. Keep a flag that says whether the current level goes left to right. For each level, create a list of exactly the level size. The k-th node popped goes to index k when going left to right, or to index size −1 minus k when going right to left. Flip the flag after every level.

Remember

Do not change the order you visit nodes, only where you write them. The index n −1 minus k reverses a level for free.

Run the animation above on your own input, or watch the 2:18 video explanation of Binary Tree Zigzag Level Order Traversal with a dry run and Java code.

More Tree problems