MediumTreeBreadth-First SearchBinary Tree

Binary Tree Zigzag Level Order Traversal

1 approach, code in every language

You are given the root of a binary tree. Return its values grouped by level, but with the reading direction alternating between levels.

The first level is read left to right, the second level right to left, the third left to right again, and so on in a zigzag pattern. The output is a list of lists, one per level, in top-to-bottom order.

The traversal order of the tree does not change; only the direction in which each level's collected values are written out flips from one level to the next.

Example 1

Input: root = [3,9,20,null,null,15,7]

Output: [[3],[20,9],[15,7]]

Level 0 reads left to right as [3]. Level 1 flips to right to left, giving [20,9]. Level 2 flips back, giving [15,7].

Example 2

Input: root = [1,2,3,4,5]

Output: [[1],[3,2],[4,5]]

The root level is [1]; the next level reversed is [3,2]; the third level returns to left-to-right as [4,5].

Constraints

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

BFS with Alternating Direction Flag

Run a normal level-order BFS but place each value into its slot based on a flipping direction flag.

Loading animation…

Intuition

The tree is still explored strictly top to bottom, left to right; only the final arrangement of each level alternates. So we keep the standard queue-based level-order sweep and add a boolean flag that flips after every level. When the flag says left to right we append values normally, and when it says right to left we insert them at the front (or compute a mirrored index) so the level ends up reversed. Deciding placement while collecting avoids a separate reversal pass and keeps the logic to a single loop per level.

Algorithm walkthrough

1Return an empty list if the root is null; otherwise seed a queue with the root and set the direction flag to left-to-right.
2While the queue is not empty, capture its size as the number of nodes on the current level.
3For each node on the level, dequeue it and place its value at the front or back of the level list according to the flag.
4Enqueue each node's non-null children so they form the next level in normal left-to-right order.
5Append the finished level to the result and flip the direction flag.
6When the queue empties, return the list of levels.

Implementation

from collections import deque

class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        result: List[List[int]] = []
        queue: deque = deque([root])
        left_to_right = True
        while queue:
            level_size = len(queue)
            level: List[int] = []
            for _ in range(level_size):
                node = queue.popleft()
                if left_to_right:
                    level.append(node.val)
                else:
                    level.insert(0, node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            result.append(level)
            left_to_right = not left_to_right
        return result

Time

O(n)

Space

O(n)

Each node is enqueued and dequeued once. Using index-based placement or a deque keeps per-level ordering at O(level size); naive front-insertion into an array can add an O(w) shift per node where w is the level width.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Binary Trees & BST

After the pattern

Now solve one you haven't seen.

Relay Tower Snake Sweep is our own problem on the technique behind Binary Tree Zigzag Level Order Traversal: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free