Binary Tree Zigzag Level Order Traversal
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 and alternate between).
- The number of nodes in the tree is in the range [0, 2000]
- −100 ≤ Node.val ≤ 100
Example
root = [3,9,20,null,null,15,7][[3],[20,9],[15,7]]The traversal starts at the root level with value 3, traversed left to right. The next level contains nodes 9 and 20, traversed right to left, so the order is [20, 9]. The final level contains nodes 15 and 7, traversed left to right again, resulting in [15, 7]. The alternating direction at each level creates the zigzag pattern.
Approach
Straightforward Solution
A naive approach performs a standard BFS level order traversal and reverses the list of node values for every alternate level after the traversal. This requires extra passes or additional space to reverse the lists.
Core Observation
A level order traversal naturally processes nodes level by level. The zigzag pattern requires reversing the order of node values at every other level, which can be achieved by controlling the insertion order of node values during traversal.
Path to Optimal
Instead of reversing after traversal, the algorithm uses a double-ended queue (deque) to insert node values either at the end or the front depending on the current traversal direction. This approach integrates the zigzag ordering into the traversal itself, avoiding extra reversal steps and maintaining O(n) time complexity.
Optimal Approach
Use a BFS queue to traverse the tree level by level. For each level, use a deque to collect node values. If traversing left to right, append values to the right; if right to left, append values to the left. After processing each level, toggle the direction flag. This approach yields the zigzag order in a single pass with O(n) time and O(n) space.
Time
O(n)
Each node is enqueued and dequeued exactly once during BFS, and each node's value is inserted into the deque once, resulting in linear time proportional to the number of nodes.
Space
O(w) (worst-case O(n))
The BFS queue and the per-level deque each store at most the number of nodes on a single level (the tree's maximum width w). Therefore the auxiliary space is O(w), which is O(n) in the worst case.
Pattern Spotlight
BFS (Level Order Traversal with Direction Toggle)
When a problem requires level order traversal with alternating processing order, integrate direction control into the traversal by using a deque and toggling insertion ends, avoiding costly post-processing reversals.
Solution
| 1 | from collections import deque |
| 2 | |
| 3 | class Solution: |
| 4 | def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]: |
| 5 | if not root: |
| 6 | return [] |
| 7 | |
| 8 | res = [] |
| 9 | q = deque([root]) |
| 10 | left_to_right = True |
| 11 | |
| 12 | while q: |
| 13 | level_size = len(q) |
| 14 | level = deque() |
| 15 | |
| 16 | for _ in range(level_size): |
| 17 | node = q.popleft() |
| 18 | |
| 19 | if left_to_right: |
| 20 | level.append(node.val) |
| 21 | else: |
| 22 | level.appendleft(node.val) |
| 23 | |
| 24 | if node.left: |
| 25 | q.append(node.left) |
| 26 | if node.right: |
| 27 | q.append(node.right) |
| 28 | |
| 29 | res.append(list(level)) |
| 30 | left_to_right = not left_to_right |
| 31 | |
| 32 | return res |
Step-by-Step Solution
Handle Empty Tree Edge Case
| 5 | if not root: |
| 6 | return [] |
Objective
To immediately return an empty list if the input tree is empty, as there are no nodes to traverse.
Key Insight
Checking for an empty root node upfront prevents unnecessary setup and traversal logic. This early exit handles the trivial case efficiently and avoids null pointer errors during BFS.
Interview Quick-Check
State & Boundaries
Return [] immediately if root is None, as no traversal is possible.
Initialize BFS Queue and Direction Flag
| 8 | res = [] |
| 9 | q = deque([root]) |
| 10 | left_to_right = True |
Objective
To set up the initial data structures for BFS traversal and track the current traversal direction.
Key Insight
The queue holds nodes to be processed level by level, starting with the root. The boolean flag `left_to_right` controls whether node values are appended to the right or left of the deque for the current level, enabling zigzag ordering.
Interview Quick-Check
Core Logic
Initialize the queue with the root node and set the direction flag to True to start traversal from left to right.
Common Pitfalls & Bugs
Forgetting to initialize the direction flag or queue correctly can cause incorrect traversal order or runtime errors.
Traverse Tree Level by Level with Zigzag Ordering
| 12 | while q: |
| 13 | level_size = len(q) |
| 14 | level = deque() |
| 16 | for _ in range(level_size): |
| 17 | node = q.popleft() |
| 19 | if left_to_right: |
| 20 | level.append(node.val) |
| 21 | else: |
| 22 | level.appendleft(node.val) |
| 24 | if node.left: |
| 25 | q.append(node.left) |
| 26 | if node.right: |
| 27 | q.append(node.right) |
| 29 | res.append(list(level)) |
| 30 | left_to_right = not left_to_right |
Objective
To perform BFS traversal, collecting node values in zigzag order by conditionally appending to the deque based on the current direction.
Key Insight
At each level, the BFS queue still dequeues nodes in left-to-right structural order. Zigzag affects only the order in which we record values. Collect values into a deque level: if left_to_right is True, append to the right; otherwise, appendleft to the left. appendleft places each newly visited value at the front, so the level is constructed in reverse order during traversal, eliminating any reversal step afterward. After processing exactly level_size nodes (the current level), append list(level) to res (output format) and toggle left_to_right (flip direction for the next level).
Interview Quick-Check
Core Logic
Process each level by dequeuing nodes, appending their values to the level deque in the correct order, enqueueing their children, and toggling the direction flag for the next level.
State & Boundaries
Use a for loop over the current queue size to ensure all nodes at the current level are processed before toggling direction.
Common Pitfalls & Bugs
Appending node values to the wrong end of the deque or toggling the direction flag incorrectly can break the zigzag pattern.
Complexity
This approach visits each node once for O(n) time and uses O(w) auxiliary space (worst-case O(n)), where w is the maximum number of nodes on any level.
Return the Zigzag Level Order Result
| 32 | return res |
Objective
To return the final list of lists containing node values in zigzag level order after traversal completes.
Key Insight
After BFS completes and all levels have been processed with alternating directions, the accumulated result list contains the desired zigzag order. Returning this list completes the solution.
Interview Quick-Check
Core Logic
Return the accumulated result list after processing all levels.
Line Analysis
This solution has 1 Critical line interviewers watch for.
level.appendleft(node.val)Insert the node value at the front of the level deque for right-to-left ordering.
This is the core zigzag operation: inserting at the front constructs the reversed order during traversal, avoiding any per-level reversal step afterward.
if not root:Check if the root node is None.
This early check prevents unnecessary processing and handles the edge case of an empty tree, ensuring the function returns immediately with an empty list.
return []Return an empty list if the tree is empty.
Returning [] here correctly signals that there are no nodes to traverse, satisfying the problem's requirement for empty input.
level = deque()Initialize a deque to collect node values for the current level.
Using a deque allows efficient insertion at both ends, which is essential for implementing zigzag ordering without extra reversal steps.
level.append(node.val)Append the node's value to the right end of the deque for left-to-right traversal.
Appending to the right preserves the natural order of nodes when traversing left to right.
res.append(list(level))Append the current level's node values as a list to the result.
Converting the deque to a list and appending it preserves the zigzag order for this level in the final output.
left_to_right = not left_to_rightToggle the traversal direction for the next level.
Flipping the direction flag ensures the zigzag pattern alternates between left-to-right and right-to-left at each level.
q = deque([root])Initialize the BFS queue with the root node.
The queue manages nodes to be processed level by level, starting with the root, enabling breadth-first traversal.
left_to_right = TrueSet the initial traversal direction to left to right.
The boolean flag controls the insertion order of node values at each level, enabling the zigzag pattern by toggling after each level.
level_size = len(q)Determine the number of nodes at the current level.
Capturing the current queue size allows processing exactly one level per iteration, maintaining level boundaries.
node = q.popleft()Dequeue the next node to process.
Removing nodes from the front of the queue maintains BFS order, processing nodes level by level.
if left_to_right:Check if the current traversal direction is left to right.
This condition determines how to insert the current node's value into the level deque to maintain zigzag order.
if node.left:Check whether the current node has a left child to enqueue.
This condition prevents enqueuing null children and ensures the next level is fully populated for BFS traversal.
q.append(node.left)Enqueue the left child into the BFS queue.
Enqueuing the left child schedules it for processing in the next BFS layer, preserving correct level boundaries and full coverage.
if node.right:Check whether the current node has a right child to enqueue.
This mirrors the left-child handling to ensure the right subtree is also traversed; omitting it would skip nodes.
q.append(node.right)Enqueue the right child into the BFS queue.
Enqueuing the right child completes adding this node’s children for the next level, maintaining BFS completeness and order.
return resReturn the final zigzag level order traversal result.
Returning the accumulated list completes the function, providing the correct zigzag traversal as required.
while q:Start the BFS loop, continuing while there are nodes to process.
The while loop ensures all levels are processed until the queue is empty, covering the entire tree.
for _ in range(level_size):Iterate over all nodes at the current level.
This loop processes each node in the current level, ensuring all nodes are handled before moving to the next level.
else:Enter the right-to-left insertion branch for this level.
This branch activates the right-to-left behavior for the current level. The actual zigzag effect is applied by the appendleft operation inside this branch.
res = []Initialize the result list to store the zigzag level order traversal.
This list accumulates the final output, collecting each level's node values in the correct zigzag order.
Test Your Understanding
Why does using a deque with conditional append or appendleft operations eliminate the need to reverse the level list after traversal?
Because inserting node values at the front or back of the deque during traversal directly constructs the zigzag order, the final list for each level is already in the correct order, making post-traversal reversal unnecessary.
Related Problems
BFS pattern
Don't just read it. Drill it.
Reconstruct Binary Tree Zigzag Level Order Traversal from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Binary Tree Zigzag Level Order Traversal drill