Generated by Codex with GPT-5
Difficulty: MEDIUM
Problem: Binary Tree Zigzag Level Order Traversal
Problem gist
The input is the root of a binary tree. The task is to return the node values level by level, but the direction alternates:
- The root level is read from left to right.
- The next level is read from right to left.
- The next level flips back to left to right, and so on.
For example, a tree with levels [3], [9, 20], and [15, 7] should return three rows: [3], then [20, 9], then [15, 7].
The key detail is that the tree structure itself does not change. Only the order in which each completed level is reported changes.
How to derive the optimal approach
Start with ordinary level order traversal. A queue naturally processes a binary tree one level at a time: pop all nodes currently in the queue, append their children for the next round, and collect the popped node values.
Zigzag traversal only adds one decision per level: should the values for this level be read left-to-right or right-to-left?
There are two clean ways to handle that decision:
- Collect values in a list, then reverse the list on every other level.
- Use a deque for the current level and insert values at the front on right-to-left levels.
Both are optimal because each node is still visited once. The deque version makes the direction change explicit and avoids a separate reverse step. Children should still be enqueued from left child to right child, because the queue should preserve the natural left-to-right structure of the next level. The direction flag only changes how the current level’s values are written into the answer.
Time complexity is O(n), where n is the number of nodes. Auxiliary space is O(w) for the BFS queue and current level, where w is the maximum tree width, plus O(n) for the returned answer.
Python solution
from collections import deque
from typing import Deque, List, Optional
class TreeNode:
"""Binary tree node. LeetCode provides an equivalent class."""
def __init__(
self,
val: int = 0,
left: Optional["TreeNode"] = None,
right: Optional["TreeNode"] = None,
) -> None:
self.val = val
self.left = left
self.right = right
class Solution:
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if root is None:
return []
traversal: List[List[int]] = []
nodes_to_visit: Deque[TreeNode] = deque([root])
read_left_to_right = True
while nodes_to_visit:
traversal.append(
self._collect_current_level(nodes_to_visit, read_left_to_right)
)
read_left_to_right = not read_left_to_right
return traversal
def _collect_current_level(
self,
nodes_to_visit: Deque[TreeNode],
read_left_to_right: bool,
) -> List[int]:
level_size = len(nodes_to_visit)
level_values: Deque[int] = deque()
for _ in range(level_size):
node = nodes_to_visit.popleft()
if read_left_to_right:
level_values.append(node.val)
else:
level_values.appendleft(node.val)
if node.left is not None:
nodes_to_visit.append(node.left)
if node.right is not None:
nodes_to_visit.append(node.right)
return list(level_values)Interview follow-ups
Can this be solved with DFS instead of BFS?
Yes. A DFS can carry the current depth along with each recursive call. When the traversal first reaches a depth, create a new bucket for that level. For even depths, append values to the end of that bucket. For odd depths, insert values at the front, usually by making each bucket a deque and converting the deques to lists at the end.
This works because a standard DFS that visits the left child before the right child sees each level in left-to-right order. Appending to the front on odd depths flips only those levels. The time complexity remains O(n), and the returned output is still O(n). The tradeoff is recursion stack space: DFS uses O(h) call stack space, where h is the tree height, and a very deep skewed tree can hit Python’s recursion limit.
Can we avoid using appendleft or reversing a list?
Yes. Since BFS knows the current level size before processing the level, allocate a fixed-size list for that level. For the ith node in the level, write to index i on left-to-right levels and to index level_size - 1 - i on right-to-left levels.
That version is also O(n) time and O(w) auxiliary space. It can be slightly faster in Python because list assignment is cheap and avoids deque-to-list conversion, but it is a little less direct to read. In an interview, either approach is acceptable as long as each node is processed once.
Why do we still enqueue children from left to right on reversed levels?
The queue is responsible for preserving the real structure of the next tree level. If children are enqueued in different orders depending on the output direction, the next level can become scrambled, especially when nodes have uneven child counts.
The safer invariant is: the queue always holds the next level from left to right. The zigzag behavior is applied only when writing values into the current level’s result. Keeping those responsibilities separate makes the algorithm easier to reason about and avoids subtle ordering bugs.
What changes if the traversal must start right-to-left?
Only the initial direction flag changes. In the BFS solution, set read_left_to_right = False before the loop. In a parity-based solution, treat even depths as right-to-left and odd depths as left-to-right.
The rest of the algorithm is identical. This is a useful follow-up because it checks whether the candidate built a general level-direction mechanism instead of hard-coding behavior around the root.
What if the interviewer asks for a streaming version?
If the caller does not need the entire nested list at once, the BFS loop can yield one completed level at a time. The queue and current-level buffer are still required, so the working space remains O(w), but the result no longer has to be stored inside the function.
This is helpful when the tree is large and the consumer can process levels incrementally. It does not reduce the total amount of output, but it can reduce peak memory owned by the traversal function.