MediumTreeBreadth-First SearchBinary TreeUpdated Sep 2026

103. Binary Tree Zigzag Level Order Traversal

Asked at Oracle, Walmart

Difficulty

Medium

Time

O(n)

Space

O(n)

Pattern

Tree

Companies

2

Problem

You are given the root of a binary tree. Return a list of lists that holds the node values level by level, but with the reading direction flipping on every level.

The first level (the root) is read left to right. The second level is read right to left. The third level is left to right again, and so on, alternating all the way down. This pattern is called a zigzag traversal.

Each inner list must contain exactly the values of one level, in the required direction. If the tree is empty, return an empty list.

Read each level, flip the direction

9[20,9]3[3]15[15,7]207level 0: left → rightlevel 1: right → leftlevel 2: left → right
Level 0 goes left to right, level 1 goes right to left, level 2 goes left to right again.

Constraints

  • ●The number of nodes in the tree is in the range [0, 2000].
  • ●-100 <= Node.val <= 100

Examples

Example 1
Inputroot = [3,9,20,null,null,15,7]
Output[[3],[20,9],[15,7]]
WhyLevel 0 has only the root, so it is [3]. Level 1 holds 9 and 20; left to right would be [9,20], but this level goes right to left, giving [20,9]. Level 2 holds 15 and 7 and is read left to right, so [15,7].
Example 2
Inputroot = [1]
Output[[1]]
WhyThere is just one node, so there is one level with one value. Direction does not matter here.
Example 3
Inputroot = []
Output[]
WhyThe tree has no nodes, so there are no levels to report.

Asked At

2 companies
CompanyDifficulty
OracleMediumView all Oracle questions →
WalmartMediumView all Walmart questions →

How to Think About It

1

Brute force: do a normal BFS level order traversal, then reverse every other level. That's O(n) time and O(n) space — same as regular BFS. The reversal step is O(level_width) per level.

2

Key insight: use BFS but track the current direction. At each level, collect nodes in order. If the level should be right-to-left, either reverse the list or insert at the front of a deque.

3

Alternative approach without reversing: use a deque. For left-to-right levels, pop from the front and push children to the back (left then right). For right-to-left levels, pop from the back and push children to the front (right then left). This avoids the O(level_width) reversal.

4

The direction flag toggles each level. Start with left-to-right (direction = 0). After processing each level, flip: direction ^= 1. Or track a boolean leftToRight and negate it each level.

5

Edge cases: empty tree (return empty list), single node (return [[val]]), skewed tree (each level has one node, zigzag is the same as normal traversal).

Optimal Approach

Use BFS with a queue. Track the current level and whether to reverse.

  1. Initialize queue with root. Set leftToRight = true.
  2. While queue is not empty:
    • Get the current level size.
    • For each node in the level, dequeue and collect its value.
    • Enqueue left child, then right child.
    • After the level, if leftToRight is false, reverse the collected values.
    • Toggle leftToRight.
  3. Return the result.

Time: O(n) — each node visited once. Reversal is O(level_width), which sums to O(n) across all levels. Space: O(n) — queue holds at most one level of nodes.

BFS queue, reverse odd levels

queue3frontbackStart: the queue holds only the rootqueue920frontbackLevel 1 collected as [9,20], then reversed to [20,9]queue157frontbackLevel 2 stays left to right: [15,7]if not left_to_right: level.reverse()left_to_right = not left_to_right
Collect each level in normal left-to-right order, then reverse it when the direction flag says so.
ComplexityTime O(n)Space O(n)Every node is dequeued once, and reversing a level costs its width, which adds up to O(n) overall; the queue holds at most one level of nodes.

What Trips People Up in Real Interviews

1

Reversing the entire result instead of alternating levels. Only reverse every other level, not the whole result. Level 0 is left-to-right, level 1 is right-to-left, and so on.

2

Using a vector and calling reverse() on odd levels. This works but is O(level_width) per reversal. Using a deque and push_front is cleaner and avoids the reversal step entirely.

3

Forgetting that the zigzag pattern applies to the VALUE order, not the node traversal order. You always enqueue left child first, then right. The zigzag only affects how you collect values.

4

Mixing up the direction at level 0. The first level (root) is left-to-right. Start with leftToRight = true and toggle AFTER processing each level.

5

Not handling null children. Skip null children when enqueueing — only add non-null children to the queue. Otherwise, you get null pointer exceptions or null values in the result.

Solution Code

O(n) time
from collections import deque

def zigzagLevelOrder(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    left_to_right = True

    while queue:
        level_size = len(queue)
        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:
            level.reverse()
        result.append(level)
        left_to_right = not left_to_right
    return result

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Binary Tree Zigzag Level Order Traversal problem?

Given a binary tree, return the zigzag level order traversal of its nodes' values. That is, traverse from left to right for the first level, then right to left for the second, and so on. This is a standard BFS variation that tests your ability to alternate traversal direction.

How do you solve Binary Tree Zigzag Level Order Traversal?

The optimal approach runs in O(n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Binary Tree Zigzag Level Order Traversal?

Binary Tree Zigzag Level Order Traversal is asked at Oracle, Walmart. It is a medium difficulty problem.

What are common mistakes on Binary Tree Zigzag Level Order Traversal?
  • Reversing the entire result instead of alternating levels. Only reverse every other level, not the whole result. Level 0 is left-to-right, level 1 is right-to-left, and so on.
  • Using a `vector` and calling `reverse()` on odd levels. This works but is `O(level_width)` per reversal. Using a `deque` and `push_front` is cleaner and avoids the reversal step entirely.
  • Forgetting that the zigzag pattern applies to the VALUE order, not the node traversal order. You always enqueue left child first, then right. The zigzag only affects how you collect values.
  • Mixing up the direction at level 0. The first level (root) is left-to-right. Start with `leftToRight = true` and toggle AFTER processing each level.
  • Not handling null children. Skip null children when enqueueing — only add non-null children to the queue. Otherwise, you get null pointer exceptions or null values in the result.