Binary Tree Zigzag Level Order Traversal

Solving tips

This is plain BFS-by-level plus one twist: the visit order never changes, only the recording order flips per level.
Track a direction flag toggled once per level; use a deque and appendleft on reversed levels to build them in O(1) per element without a separate reverse pass.
Snapshot len(queue) before the inner loop, and toggle the direction outside the inner loop (once per level), not per node.
Don't reverse the node-visit order (e.g. enqueuing right first), which corrupts the next level; return [] not [[]] for an empty tree. Target O(n) time and space.

Problem

You are given the root of a binary tree. Return the values of its nodes grouped by level (depth), but with the direction alternating: the first level is listed left-to-right, the second level right-to-left, the third left-to-right again, and so on.

The answer is a list of lists — one inner list per level, ordered from the root level downward, with each inner list already in its zigzag direction.

Examples

Example 1

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

        3
       / \
      9   20
         /  \
        15   7

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

Level 0 goes left-to-right ([3]), level 1 flips ([20, 9]), level 2 flips back ([15, 7]).

Example 2

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

Odd-indexed levels are reversed; even-indexed levels keep natural order.

Example 3

Input:  root = []
Output: []

An empty tree produces an empty answer.

Constraints

The number of nodes is in the range [0, 2000].
-100 <= Node.val <= 100
Expected complexity: O(n) time — every node must be visited exactly once.

Think about it first

Hint 1

Do you already know how to produce a plain level-order traversal? Zigzag is that traversal plus one small twist.

Hint 2

Keep a flag (or use the level's index parity) telling you whether the current level should be reversed. You never need to change the order in which you *visit* nodes.

Hint 3

Standard BFS with a queue: pop one full level at a time into a list, then either append the list as-is or reversed depending on the level's parity. Alternatively, a deque lets you build each level in the correct order directly by choosing which end you write to.

TL;DR

BFS level by level, reversing (or deque-building) alternate levels — O(n) time, O(n) space.

Approach 1 — Brute force

There is no meaningfully worse brute force here: any correct answer must visit all n nodes, so the “naive” starting point is a plain BFS followed by reversing every other level after the fact.

# 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

from collections import deque
from typing import List, Optional


class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        levels: List[List[int]] = []
        queue = deque([root])
        while queue:
            level = []
            for _ in range(len(queue)):
                node = queue.popleft()
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            levels.append(level)
        # post-pass: flip odd levels
        for i in range(1, len(levels), 2):
            levels[i].reverse()
        return levels

Complexity: O(n) time, O(n) space. The constraints (≤ 2000 nodes) don’t “kill” this — it’s already optimal asymptotically; the refinement below just folds the reversal into the traversal.

Approach 2 — BFS with a direction flag (canonical)

The insight: you never need to visit nodes in a different order — only the recording order flips. Track a boolean that toggles per level and reverse each level list as you commit it (or slice-reverse on append).

# 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

from collections import deque
from typing import List, Optional


class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        result: List[List[int]] = []
        queue = deque([root])
        left_to_right = True
        while queue:
            level: deque[int] = deque()
            for _ in range(len(queue)):
                node = queue.popleft()
                if left_to_right:
                    level.append(node.val)      # write at the right end
                else:
                    level.appendleft(node.val)  # write at the left end
                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

Using appendleft on a deque builds reversed levels in O(1) per element, so no separate reversal pass is needed. (BFS — breadth-first search — is the classical algorithm here: it explores a graph/tree in expanding “rings” of distance from the start, which for trees means level by level.)

Walkthrough on Example 1 (root = [3, 9, 20, null, null, 15, 7]):

Step	queue before	direction	level built	result so far
1	`[3]`	L→R	`[3]`	`[[3]]`
2	`[9, 20]`	R→L	pop 9 → `[9]`, pop 20 → appendleft → `[20, 9]`	`[[3], [20, 9]]`
3	`[15, 7]`	L→R	`[15, 7]`	`[[3], [20, 9], [15, 7]]`

Complexity: O(n) time — each node enqueued/dequeued once; O(n) space — the queue holds up to the widest level (worst case ~n/2 nodes), plus the output.

Approach 3 — DFS with depth bookkeeping

The insight: BFS is not required to group by level. A DFS that carries the current depth can drop each value into result at index depth; the zigzag is handled by which end of that level’s list you insert at, based on depth parity. Preorder DFS visits left children before right, which is exactly left-to-right order within a level.

# 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

from collections import deque
from typing import List, Optional


class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        result: List[deque] = []

        def dfs(node: Optional[TreeNode], depth: int) -> None:
            if not node:
                return
            if depth == len(result):
                result.append(deque())
            if depth % 2 == 0:
                result[depth].append(node.val)
            else:
                result[depth].appendleft(node.val)
            dfs(node.left, depth + 1)
            dfs(node.right, depth + 1)

        dfs(root, 0)
        return [list(level) for level in result]

Walkthrough on Example 1: dfs(3,0) → result=[[3]]; dfs(9,1) → depth 1 is odd, appendleft → [[3],[9]]; dfs(20,1) → appendleft → [[3],[20,9]]; dfs(15,2) → [[3],[20,9],[15]]; dfs(7,2) → [[3],[20,9],[15,7]].

Complexity: O(n) time; O(h) recursion stack plus O(n) output, where h is tree height.

Common pitfalls

Forgetting to snapshot len(queue) before the inner loop — consuming the queue with a plain while queue mixes levels together.
Reversing the visit order (e.g., pushing right child first on odd levels) instead of the record order; it’s easy to corrupt the next level’s ordering that way.
Toggling the direction flag inside the inner loop instead of once per level.
Returning [[]] instead of [] for an empty tree.

Pattern takeaway

Level-order variants are almost never new traversals — they are plain BFS plus a per-level post-processing rule (reverse, sum, rightmost element, average…). When a problem says “by level, but…”, write the standard for _ in range(len(queue)) BFS skeleton first, then bolt the twist onto the point where a completed level is committed to the answer.