Binary Tree · BFS
Visual EditorTree Problems

Binary Tree Zigzag Level Order Traversal

Level-order traversal where each level alternates direction — left→right, then right→left, then left→right…

BFS + DequeLevel-by-LevelDirection FlagMedium

Key concepts at a glance — for those who already know the basics.

Problem Statement

Binary Tree Zigzag Level Order Traversal

Given the root of a binary tree, return the zigzag level order traversal where level order is preserved but the output direction alternates at every depth.
Example

Input: root = [3, 9, 20, null, null, 15, 7]

Output: [[3], [20, 9], [15, 7]]

Constraints

  • The number of nodes in the tree is in range [0, 2000].
  • Node values are in range [-100, 100].

01 · The rule

BFS level-by-level, but flip the collection direction each level

Use a standard BFS queue. After collecting each level's nodes, check a boolean flag: if left_to_right is True, keep the level as-is; otherwise reverse it before appending to results. Toggle the flag after every level.

02 · How to think

1
BFS level by level — collect all nodes at each depth
Use len(queue) at the start of each iteration to know exactly how many nodes belong to the current level.
2
Reverse the level list when going right→left
Level 0 (root): left→right. Level 1: right→left. Level 2: left→right. Toggle left_to_right after every level.
3
Append (possibly reversed) level to result
Children are always enqueued left-then-right — only the output list is reversed. The queue order never changes.

03 · Code (Python)

from collections import deque

def zigzagLevelOrder(root):
    if not root: return []
    result        = []
    queue         = deque([root])          # standard BFS queue
    left_to_right = True                   # direction flag

    while queue:
        level_size = len(queue)           # freeze current level count
        level      = []

        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            if node.left:  queue.append(node.left)
            if node.right: queue.append(node.right)

        if not left_to_right:   # flip if right-to-left level
            level.reverse()
        result.append(level)
        left_to_right = not left_to_right  # toggle for next level

    return result

04 · Example tree & zigzag output

L0L1L2L→RR→LL→R3920157right → leftleft → rightOutput: [[3], [20, 9], [15, 7]]
Level
Direction
Nodes collected
After flip?
0
L → R
[3]
No flip → [3]
1
R → L
[9, 20]
Reversed → [20, 9]
2
L → R
[15, 7]
No flip → [15, 7]

05 · Complexity

Time
O(n)
Every node is enqueued and dequeued exactly once. Reversing a level costs O(w) where w is the level width — summing across all levels gives O(n) total.
Space
O(n)
Queue holds at most O(w) nodes (widest level). Result list stores all n values. Both bounded by O(n).

Ready to see it in action?

Step through the visualizer to watch the algorithm state update live.

Open Visualizer