LeetCode 103: Binary Tree Zigzag Level Order Traversal

Problem Restatement

We are given the root of a binary tree.

We need to return the values level by level. The first level is read from left to right, the second level from right to left, the third level from left to right, and so on.

The official problem asks for the zigzag level order traversal of a binary tree’s node values.

For this tree:

        3
      /   \
     9     20
          /  \
         15   7

The normal level order traversal would be:

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

The zigzag level order traversal is:

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

The second level is reversed.

Input and Output

LeetCode gives the TreeNode class:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

The function shape is:

class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> list[list[int]]:
        ...

Examples

Consider this tree:

        3
      /   \
     9     20
          /  \
         15   7

Level 0 is read left to right:

[3]

Level 1 is read right to left:

[20, 9]

Level 2 is read left to right:

[15, 7]

So the answer is:

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

For a single-node tree:

1

The answer is:

[[1]]

For an empty tree, the answer is:

[]

First Thought: Use Normal Level Order Traversal

The problem still asks for values grouped by level.

That means breadth-first search is the natural traversal method.

The only difference from normal level order traversal is the order of values inside each level.

We can still visit nodes left to right with a queue. After collecting one level, we decide whether to keep it as is or reverse it.

Key Insight

The traversal order and output order can be handled separately.

The queue should always process nodes in normal left-to-right order:

node.left before node.right

This keeps the next level organized correctly.

Then, for each level, use a boolean flag:

left_to_right = True

If left_to_right is true, append the level values normally.

If it is false, append the reversed level values.

After each level, flip the flag.

Algorithm

If root is None, return [].

Otherwise:

1. Create a queue containing root.
2. Create an empty answer list.
3. Set left_to_right = True.
4. While the queue has nodes:
   1. Create an empty list for the current level.
   2. Read the current queue size.
   3. Process exactly that many nodes.
   4. Append each node value to the current level list.
   5. Add the left child if it exists.
   6. Add the right child if it exists.
   7. If the direction is right to left, reverse the level list.
   8. Append the level list to the answer.
   9. Flip the direction.
5. Return the answer.

Correctness

The queue begins with the root, so the first processed group is level 0.

At the start of each outer loop, the queue contains exactly the nodes of the current level in left-to-right order. We store the queue size before processing the level, so nodes added during this loop are saved for the next level.

For every node, the algorithm adds the left child before the right child. Therefore, the next level is also stored in left-to-right order in the queue.

The algorithm then uses left_to_right to choose the output order for the current level. On even-numbered levels, it keeps the collected values in left-to-right order. On odd-numbered levels, it reverses them, producing right-to-left order.

After each level, the flag is flipped. Therefore, the output direction alternates on every level.

So every level is included exactly once, every node value appears in the correct level, and the direction alternates as required.

Complexity

Here, n is the number of nodes in the tree.

Reversing a level costs time proportional to that level’s size. Across the whole tree, all reversals together still cost O(n).

Implementation

from collections import deque
from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> list[list[int]]:
        if root is None:
            return []

        ans = []
        q = deque([root])
        left_to_right = True

        while q:
            level = []

            for _ in range(len(q)):
                node = q.popleft()
                level.append(node.val)

                if node.left is not None:
                    q.append(node.left)

                if node.right is not None:
                    q.append(node.right)

            if not left_to_right:
                level.reverse()

            ans.append(level)
            left_to_right = not left_to_right

        return ans

Code Explanation

We first handle the empty tree:

if root is None:
    return []

Then we create the queue:

q = deque([root])

The direction flag starts as True because the first level is read left to right:

left_to_right = True

The outer loop processes one level at a time:

while q:

For each level, we collect values in normal left-to-right order:

level = []

This loop runs only for the nodes already in the current level:

for _ in range(len(q)):

Each node is removed from the front of the queue:

node = q.popleft()

Then its value is stored:

level.append(node.val)

The children are added from left to right:

if node.left is not None:
    q.append(node.left)

if node.right is not None:
    q.append(node.right)

If the current level should be read right to left, we reverse the collected values:

if not left_to_right:
    level.reverse()

Then we store the level and flip the direction:

ans.append(level)
left_to_right = not left_to_right

Finally:

return ans

Testing

from collections import deque
from typing import Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> list[list[int]]:
        if root is None:
            return []

        ans = []
        q = deque([root])
        left_to_right = True

        while q:
            level = []

            for _ in range(len(q)):
                node = q.popleft()
                level.append(node.val)

                if node.left is not None:
                    q.append(node.left)

                if node.right is not None:
                    q.append(node.right)

            if not left_to_right:
                level.reverse()

            ans.append(level)
            left_to_right = not left_to_right

        return ans

def run_tests():
    s = Solution()

    root1 = TreeNode(
        3,
        TreeNode(9),
        TreeNode(20, TreeNode(15), TreeNode(7)),
    )
    assert s.zigzagLevelOrder(root1) == [[3], [20, 9], [15, 7]]

    root2 = TreeNode(1)
    assert s.zigzagLevelOrder(root2) == [[1]]

    root3 = None
    assert s.zigzagLevelOrder(root3) == []

    root4 = TreeNode(
        1,
        TreeNode(2, TreeNode(4), TreeNode(5)),
        TreeNode(3, TreeNode(6), TreeNode(7)),
    )
    assert s.zigzagLevelOrder(root4) == [[1], [3, 2], [4, 5, 6, 7]]

    root5 = TreeNode(
        1,
        TreeNode(2, TreeNode(3, TreeNode(4))),
        None,
    )
    assert s.zigzagLevelOrder(root5) == [[1], [2], [3], [4]]

    print("all tests passed")

run_tests()

Test meaning: