Skip to main content

70. Binary Tree Zigzag Level Order Traversal

mediumAsked at Vercel

Return the zigzag level-order traversal (alternate left-to-right and right-to-left) of a binary tree. Vercel asks this as a small twist on BFS — the same shape with a per-level direction flag.

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

Source citations

Public interview reports confirming this problem appears in Vercel loops.

  • Glassdoor (2025-12)— Vercel platform onsite; level-direction toggle expected.
  • Blind (2026-Q1)— Listed in Vercel screen pool.

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 every other level

Do standard BFS; reverse the levels at odd depths.

Time
O(n)
Space
O(w)
function zigzagLevelOrder(root) {
  if (!root) return [];
  const out = [];
  let q = [root];
  let leftToRight = true;
  while (q.length) {
    const level = [];
    const next = [];
    for (const node of q) {
      level.push(node.val);
      if (node.left) next.push(node.left);
      if (node.right) next.push(node.right);
    }
    if (!leftToRight) level.reverse();
    out.push(level);
    leftToRight = !leftToRight;
    q = next;
  }
  return out;
}

Tradeoff: Simple and clear. The reverse adds O(n) total work spread across levels.

2. BFS + deque with bidirectional push (alternative)

Use a deque; push back when going left-to-right, push front when going right-to-left.

Time
O(n)
Space
O(w)
// Same complexity; uses a deque to avoid the reverse step.

Tradeoff: Slightly more code; mention as an alternative.

Vercel-specific tips

Vercel grades the BFS structure plus the direction toggle. Bonus signal: noting that reverse() is O(n) per level but still O(n) total across the tree. Mention the deque alternative as a constant-factor win.

Common mistakes

  • Toggling direction inside the inner loop — reverses some nodes mid-level.
  • Reversing children push order (enqueuing right before left) — affects the WHOLE traversal, not just direction.
  • Off-by-one on leftToRight — first level should be left-to-right.

Follow-up questions

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

  • Custom direction pattern (e.g., every third level reversed).
  • Spiral traversal — same shape with 3+ directions.
  • Vertical order traversal (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 not reverse the enqueue order?

That would flip the next level's children too, cascading the reversal. The direction toggle should only affect the EMITTED level, not the BFS queue.

Deque vs reverse — which is faster?

Deque saves the O(n) reverse pass. In JavaScript, Array.unshift is O(n) anyway, so a real deque (e.g., a doubly linked list) is needed for true O(1) front insertion.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →