Skip to main content

103. Binary Tree Zigzag Level Order Traversal

mediumAsked at Microsoft

Binary Tree Zigzag Level Order Traversal is Microsoft's BFS-with-a-twist medium. Do a normal level-order BFS, then reverse alternate levels at the end. The cleaner trick is using a deque-as-output and toggling push direction every level.

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

Source citations

Public interview reports confirming this problem appears in Microsoft loops.

  • Glassdoor (2026-Q1)— Microsoft Azure/Office org onsite reports list Zigzag Traversal as a recurring 30-minute BFS medium.
  • Blind (2025-12)— Microsoft L60/L61 reports include Zigzag as the alternate-direction follow-up after Level Order (LC 102).

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]]

Example 3

Input
root = []
Output
[]

Approaches

1. BFS with per-level direction toggle (optimal)

Standard level-order BFS, but maintain a leftToRight flag that flips each level. Push each level's values to the front of the output array when going right-to-left.

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

Tradeoff: Linear time, linear space. The unshift is O(level size), but level size is bounded so the total work stays O(n). The 'always enqueue left then right' invariant — independent of direction — is key; only the OUTPUT order flips.

2. Level-order BFS then reverse alternate levels

Do a vanilla level-order traversal. After collecting all levels, reverse the odd-indexed levels.

Time
O(n)
Space
O(n)
function zigzagLevelOrder(root) {
  if (!root) return [];
  const result = [];
  const queue = [root];
  while (queue.length) {
    const size = queue.length;
    const level = [];
    for (let i = 0; i < size; i++) {
      const node = queue.shift();
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
  }
  for (let i = 1; i < result.length; i += 2) result[i].reverse();
  return result;
}

Tradeoff: Cleaner separation of 'traverse' and 'transform' but does a second pass. Microsoft accepts both. Lead with the toggle version; mention this as the alternative if asked.

Microsoft-specific tips

Microsoft's grading is on whether you keep the enqueue order CONSISTENT (left child first, then right) while flipping only the OUTPUT direction. Candidates who try to flip the enqueue order tie themselves in knots. Say out loud: 'the tree shape doesn't change, only how I read the level out.' Then write the toggle.

Common mistakes

  • Flipping enqueue order — produces correct values but in a tangled way that's hard to follow.
  • Using unshift inside a hot loop in a language where unshift is O(n) on every call — JavaScript Array.unshift is exactly this. For large levels, push then reverse the level once at the end is faster.
  • Forgetting to handle empty root.

Follow-up questions

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

  • Binary Tree Level Order Traversal (LC 102) — same shape without the zigzag.
  • Binary Tree Right Side View (LC 199) — also a BFS variant.
  • What if you needed to do this for an N-ary tree?

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 flip the enqueue order?

It works but doubles the code complexity — you'd push right then left on alternate levels, which conflates 'tree traversal' with 'output order.' Keeping enqueue consistent and flipping only the output is cleaner.

Is the unshift cost a real problem?

For typical tree sizes (n <= 2000 per LeetCode constraints), no. For production-scale trees, prefer level.push() + level.reverse() at the end of each level.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →