Zigzag Level Order

35 min · zigzagLevelOrder()

Picture ushers checking theater rows: they cross the first row left to right, turn around for the next, then keep switching direction without skipping a seat.

Given the root of a binary tree, return its values one level at a time in zigzag order — alternating the reading direction on each depth. Read depth 0 from left to right, depth 1 from right to left, depth 2 from left to right, and so on.

Keep these rules straight:

Return one inner array per depth, ordered from the root downward.
Switching direction changes only the output order; it doesn't change the tree.
Return [] for an empty tree.

Constraints

0 <= node count <= 10_000
-1_000 <= node.val <= 1_000

Hints

Separate collecting from turning

First collect every level from left to right. Once that works, reverse the arrays at odd-numbered depths.

Freeze the current level

Save the queue length before processing a level. Children can join the queue, but only the saved number of nodes belongs in the current inner array.

Track one bit of state

A boolean can tell you whether the current level keeps its order or reverses. Flip it after finishing the whole level, not after every node.

Follow-up

Can you collect the same levels with depth-first traversal first, then apply the alternating reversals afterward?

Visible cases

Examples

Example 1

ready

Input: root = [ 3, 9, 20, null, null, 15, 7 ]
Expected: [ [ 3 ], [ 20, 9 ], [ 15, 7 ] ]
Why: the middle level reverses, then the direction switches back

Example 2

ready

Input: root = []
Expected: []
Why: an empty tree has no levels

Example 3

ready

Input: root = [ 1 ]
Expected: [ [ 1 ] ]
Why: a single level reads left to right

Interview signal

Asked at

AmazonMetaMicrosoft

DFS then reverse — build the levels first

A depth-first search (DFS) follows one branch before coming back. Carry each node's depth on a stack, a last-in, first-out collection, append its value to that depth's bucket, then reverse every odd-numbered bucket.

def zigzag_level_order(root: TreeNode | None) -> list[list[int]]:
    if root is None:
        return []
 
    levels: list[list[int]] = []
    stack: list[tuple[TreeNode, int]] = [(root, 0)]
 
    while stack:
        node, depth = stack.pop()
        if depth == len(levels):
            levels.append([])
        levels[depth].append(node.val)
 
        if node.right is not None:
            stack.append((node.right, depth + 1))
        if node.left is not None:
            stack.append((node.left, depth + 1))
 
    for depth in range(1, len(levels), 2):
        levels[depth].reverse()
    return levels

Pushing the right child before the left makes the stack process left-side nodes first, so every bucket begins in normal left-to-right order.

Time O(n) — collect and reverse each value once. Space O(n) — the result plus the pending DFS stack.

Level-order queue — turn after each row

The core pattern is breadth-first level-order traversal (BFS): visit every node at one depth before the next, using a queue, a first-in, first-out collection. The level-size trick means saving len(queue) before the inner loop so newly enqueued children can't enter the current level.

from collections import deque
 
 
def zigzag_level_order(root: TreeNode | None) -> list[list[int]]:
    if root is None:
        return []
 
    answer: list[list[int]] = []
    queue = deque([root])
    left_to_right = True
 
    while queue:
        level_size = len(queue)
        level: list[int] = []
 
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            if node.left is not None:
                queue.append(node.left)
            if node.right is not None:
                queue.append(node.right)
 
        if not left_to_right:
            level.reverse()
        answer.append(level)
        left_to_right = not left_to_right
 
    return answer

Collect normally and reverse once per odd level. Inserting every value at the front of a Python list would repeatedly shift existing values and can make a wide level quadratic — its work grows with the square of the level's size.

Time O(n) — every node is queued once, and every odd level is reversed once. Space O(n) — the returned levels and the queue together hold O(n) values.

Loading editor

Console

ready to run

Ready to run.

3 cases are queued.

Visible testcase

Case 1

Arguments · JSON arrayroot: TreeNode

Expected

Run: visible + custom · Submit: full suite