75. Binary Tree Zigzag Level Order Traversal

Q: Why a deque in production?

Array.unshift is O(k). A deque (double-ended queue) gives O(1) push to both ends. For very wide trees the constant matters.

Q: How does this map to alternating-direction aggregation?

Some window functions (e.g., percentile_disc) want alternating-direction passes over partitions. The flip-flag pattern here generalizes.

mediumAsked at Snowflake

BFS but alternate left-to-right and right-to-left per level. Snowflake asks this to test BFS with a flip — direct analog to alternating-direction aggregation in window functions over partitioned streams.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-20

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

Glassdoor (2025-Q4)— Snowflake execution-engine team uses this in onsites.
LeetCode Discuss (2025-09)— Reported at Snowflake new-grad screens.

Problem

Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between).

Constraints

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

Examples

Example 1

Input

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

Output

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

Example 2

Input

root = [1]

Output

[[1]]

Approaches

1. BFS then reverse odd levels

Plain BFS, then reverse the resulting array at odd indices.

Time: O(n)
Space: O(n)

// outline: do plain BFS, then for each odd-index level reverse it.

Tradeoff: Works but does an extra pass over level data.

2. BFS with direction toggle (optimal)

BFS; track a 'reverse' flag. Insert values at front or back of the current level array based on flag.

Time: O(n)
Space: O(width)

function zigzagLevelOrder(root) {
  if (!root) return [];
  const result = [];
  let queue = [root];
  let reverse = false;
  while (queue.length) {
    const level = [];
    const next = [];
    for (const n of queue) {
      if (reverse) level.unshift(n.val);
      else level.push(n.val);
      if (n.left) next.push(n.left);
      if (n.right) next.push(n.right);
    }
    result.push(level);
    queue = next;
    reverse = !reverse;
  }
  return result;
}

Tradeoff: Single pass. Note: unshift is O(k). For interview purposes that's fine; in production use a deque.

Snowflake-specific tips

Snowflake interviewers want the BFS-with-flip pattern. Bonus signal: discuss how unshift's O(k) cost balloons for wide trees, and how a deque (or two stacks) gives true O(1) insert at both ends — relevant for any direction-alternating stream processing.

Common mistakes

Mutating queue while iterating (instead of building a 'next' list).
Forgetting to flip the direction every level.
Using unshift in a tight loop and not noting the asymptotic cost.

Follow-up questions

An interviewer at Snowflake may pivot to one of these next:

Vertical Order Traversal (LC 987).
Level Order from Right to Left.
Implement with a deque for true O(1) insert.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why a deque in production?

Array.unshift is O(k). A deque (double-ended queue) gives O(1) push to both ends. For very wide trees the constant matters.

How does this map to alternating-direction aggregation?

Some window functions (e.g., percentile_disc) want alternating-direction passes over partitions. The flip-flag pattern here generalizes.

Practice these live with InterviewChamp.AI

Drill Binary Tree Zigzag Level Order Traversal and other Snowflake interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →