Zigzag Level Order Traversal

MediumTree BFSMidOpen on LeetCodeUpdated Sep 21, 2026

You're given the root of a binary tree. Return its values level by level as a list of lists, alternating direction: depth 0 (the root) is read left to right, depth 1 right to left, depth 2 left to right again, and so on. An empty tree returns an empty list. Example trees are listed row by row from the top, each row left to right, with null where a child is missing.

Examples

root = [3,9,20,null,null,15,7] returns [[3],[20,9],[15,7]]

Depth 0 reads left to right: [3]. Depth 1 reads right to left, so 9, 20 becomes [20,9]. Depth 2 flips back to left to right: [15,7].

root = [1] returns [[1]]

A single node is one level, read left to right.

root = [1,2,3,4,5,6,7,8,null,null,null,null,null,null,9] returns [[1],[3,2],[4,5,6,7],[9,8]]

Depth 3 reads right to left: 9, then 8.

The first three depths give [1], [3,2] and [4,5,6,7]. Depth 3 holds 8 and 9 from opposite ends of the tree, and it is read right to left, so 9 comes first.

Constraints

0 <= number of nodes <= 2000

Hints

Hint 1

What would change about level-order if every other row were emitted in the opposite order?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Run a normal level-by-level traversal with a queue, always pushing children left then right, and keep a leftToRight flag that starts true and flips after every level. While popping a level, append each value to the back of a deque when the flag is true and to the front when it is false, which produces the reversed order directly. O(n) time, O(n) space.

Time

O(n)

Space

O(n)

Pitfall

Changing the order you push children onto the queue on reversed levels. That scrambles every level after it; keep the queue in plain left-to-right order and flip only the order you record values.

Solutions

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        boolean leftToRight = true;
        while (!queue.isEmpty()) {
            int size = queue.size();
            LinkedList<Integer> level = new LinkedList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (leftToRight) level.addLast(node.val);
                else level.addFirst(node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            result.add(level);
            leftToRight = !leftToRight;
        }
        return result;
    }
}

from collections import deque

class Solution:
    def zigzagLevelOrder(self, root):
        result = []
        if not root:
            return result
        queue = deque([root])
        left_to_right = True
        while queue:
            level = deque()
            for _ in range(len(queue)):
                node = queue.popleft()
                if left_to_right:
                    level.append(node.val)
                else:
                    level.appendleft(node.val)
                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