Problem
You are given the root of a binary tree. Return the values of its nodes grouped by level (depth), but with the direction alternating: the first level is listed left-to-right, the second level right-to-left, the third left-to-right again, and so on.
The answer is a list of lists — one inner list per level, ordered from the root level downward, with each inner list already in its zigzag direction.
Examples
Example 1
Input: root = [3, 9, 20, null, null, 15, 7]
3
/ \
9 20
/ \
15 7
Output: [[3], [20, 9], [15, 7]]
Level 0 goes left-to-right ([3]), level 1 flips ([20, 9]), level 2 flips back ([15, 7]).
Example 2
Input: root = [1, 2, 3, 4, 5, 6, 7]
Output: [[1], [3, 2], [4, 5, 6, 7]]
Odd-indexed levels are reversed; even-indexed levels keep natural order.
Example 3
Input: root = []
Output: []
An empty tree produces an empty answer.
Constraints
- The number of nodes is in the range
[0, 2000].
-100 <= Node.val <= 100- Expected complexity:
O(n) time — every node must be visited exactly once.
Think about it first
Hint 1
Do you already know how to produce a plain level-order traversal? Zigzag is that traversal plus one small twist.
Hint 2
Keep a flag (or use the level's index parity) telling you whether the current level should be reversed. You never need to change the order in which you *visit* nodes.
Hint 3
Standard BFS with a queue: pop one full level at a time into a list, then either append the list as-is or reversed depending on the level's parity. Alternatively, a deque lets you build each level in the correct order directly by choosing which end you write to.
TL;DR
BFS level by level, reversing (or deque-building) alternate levels — O(n) time, O(n) space.
Approach 1 — Brute force
Any correct answer must visit all n nodes, so there is no asymptotically worse brute force. The naive starting point is a plain BFS, then reverse every other level afterward.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
from collections import deque
from typing import List, Optional
def zigzagLevelOrder(root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
levels: List[List[int]] = []
queue = deque([root])
while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
levels.append(level)
# post-pass: flip odd levels
for i in range(1, len(levels), 2):
levels[i].reverse()
return levels
Complexity: O(n) time, O(n) space. This is already asymptotically optimal; the refinement below folds the reversal into the traversal.
Approach 2 — BFS with a direction flag (canonical)
The insight: the recording order flips, not the visit order. Track a boolean that toggles per level, and write each value to the correct end of the level list as you go.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
from collections import deque
from typing import List, Optional
def zigzagLevelOrder(root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
result: List[List[int]] = []
queue = deque([root])
left_to_right = True
while queue:
level: deque[int] = deque()
for _ in range(len(queue)):
node = queue.popleft()
if left_to_right:
level.append(node.val) # write at the right end
else:
level.appendleft(node.val) # write at the left end
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(list(level))
left_to_right = not left_to_right
return result
Using appendleft on a deque builds reversed levels in O(1) per element, so no separate reversal pass is needed. BFS (breadth-first search) processes the tree level by level, which is exactly the grouping the problem asks for.
The tree in Example 1:
flowchart TD
A[3] --> B[9]
A[3] --> C[20]
C --> D[15]
C --> E[7]
Walkthrough on Example 1 (root = [3, 9, 20, null, null, 15, 7]):
| Step | queue before | direction | level built | result so far |
|---|
| 1 | [3] | L→R | [3] | [[3]] |
| 2 | [9, 20] | R→L | pop 9 → [9], pop 20 → appendleft → [20, 9] | [[3], [20, 9]] |
| 3 | [15, 7] | L→R | [15, 7] | [[3], [20, 9], [15, 7]] |
Complexity: O(n) time — each node enqueued/dequeued once; O(n) space — the queue holds up to the widest level (worst case ~n/2 nodes), plus the output.
Approach 3 — DFS with depth bookkeeping
The insight: BFS is not required to group by level. A DFS that carries the current depth can place each value into result at index depth; the zigzag is handled by which end of that level’s list you insert at, based on depth parity. Preorder DFS visits left children before right, which is exactly left-to-right order within a level.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
from collections import deque
from typing import List, Optional
def zigzagLevelOrder(root: Optional[TreeNode]) -> List[List[int]]:
result: List[deque] = []
def dfs(node: Optional[TreeNode], depth: int) -> None:
if not node:
return
if depth == len(result):
result.append(deque())
if depth % 2 == 0:
result[depth].append(node.val)
else:
result[depth].appendleft(node.val)
dfs(node.left, depth + 1)
dfs(node.right, depth + 1)
dfs(root, 0)
return [list(level) for level in result]
Walkthrough on Example 1: dfs(3,0) → result=[[3]]; dfs(9,1) → depth 1 is odd, appendleft → [[3],[9]]; dfs(20,1) → appendleft → [[3],[20,9]]; dfs(15,2) → [[3],[20,9],[15]]; dfs(7,2) → [[3],[20,9],[15,7]].
Complexity: O(n) time; O(h) recursion stack plus O(n) output, where h is tree height.
Common pitfalls
- Forgetting to snapshot
len(queue) before the inner loop — consuming the queue with a plain while queue mixes levels together.
- Reversing the visit order (e.g., pushing right child first on odd levels) instead of the record order; it’s easy to corrupt the next level’s ordering that way.
- Toggling the direction flag inside the inner loop instead of once per level.
- Returning
[[]] instead of [] for an empty tree.
Pattern takeaway
Level-order variants are rarely new traversals. They are plain BFS plus a per-level post-processing rule (reverse, sum, rightmost element, average, and so on). When a problem says “by level, but…”, write the standard for _ in range(len(queue)) BFS skeleton first, then apply the twist at the point where a completed level is committed to the answer.