Skip to main content

65. Binary Tree Zigzag Level Order Traversal

mediumAsked at Reddit

Return zigzag level-order traversal of a binary tree. Reddit asks this as a BFS variation to test deque vs. queue intuition — relevant for their alternating-direction rendering pattern in certain UI experiments.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Reddit loops.

  • Glassdoor (2026-Q1)— Reddit phone screen, common BFS twist.

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 + reverse alternate levels

Standard BFS; reverse every other level before pushing to result.

Time
O(n)
Space
O(w)
function zigzagLevelOrder(root) {
  if (!root) return [];
  const out = [];
  const q = [root];
  let leftToRight = true;
  while (q.length) {
    const size = q.length;
    const level = [];
    for (let i = 0; i < size; i++) {
      const n = q.shift();
      level.push(n.val);
      if (n.left) q.push(n.left);
      if (n.right) q.push(n.right);
    }
    if (!leftToRight) level.reverse();
    out.push(level);
    leftToRight = !leftToRight;
  }
  return out;
}

Tradeoff: Clean. Reverse is O(width) — same as the level itself.

2. BFS with deque + direction (optimal)

Use a deque-like array. Insert at front or back based on direction.

Time
O(n)
Space
O(w)
function zigzagLevelOrder(root) {
  if (!root) return [];
  const out = [];
  const q = [root];
  let leftToRight = true;
  while (q.length) {
    const size = q.length;
    const level = new Array(size);
    for (let i = 0; i < size; i++) {
      const n = q.shift();
      level[leftToRight ? i : size - 1 - i] = n.val;
      if (n.left) q.push(n.left);
      if (n.right) q.push(n.right);
    }
    out.push(level);
    leftToRight = !leftToRight;
  }
  return out;
}

Tradeoff: Same complexity, avoids the final reverse. Cleaner.

Reddit-specific tips

Reddit interviewers will accept either. Bonus signal: choose the deque/index-fill variant — explain that it avoids the reverse pass and keeps the per-level work uniform.

Common mistakes

  • Reversing the queue itself (breaks BFS).
  • Flipping direction mid-level (must flip after each level).
  • Using level.reverse() in-place — fine; just don't double-flip.

Follow-up questions

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

  • Level order (LC 102) — without zigzag.
  • N-ary level order traversal (LC 429).
  • Vertical order (LC 314).

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 is deque preferred?

Avoids the extra O(w) reverse. Both have the same big-O, but cleaner code.

Direction starts left-to-right?

Yes per the problem; level 0 has only the root so direction doesn't matter for level 0.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →