Skip to main content

63. Binary Tree Zigzag Level Order Traversal

mediumAsked at Workday

Return the zigzag (alternating left-to-right then right-to-left) traversal of a binary tree. Workday uses this to test BFS + per-level transformation — same pattern as alternating row directions when emitting a multi-level approval-chain report.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2025)— Workday SDE2 phone screen.

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 level-order BFS. Reverse level array on odd levels.

Time
O(n)
Space
O(n)
// standard BFS, then result.push(leftToRight ? level : level.reverse())

Tradeoff: Easy but performs an explicit reverse.

2. BFS with deque-style level build

BFS. For each level, build by pushing front or back based on direction.

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

Tradeoff: Pre-allocated level array; index from front or back. No explicit reverse.

Workday-specific tips

Workday accepts either reverse-on-odd or pre-allocate-with-index. The pre-allocate version avoids the explicit reverse pass — slightly more efficient and a stronger signal.

Common mistakes

  • Forgetting to flip leftToRight after each level.
  • Reversing during queue enqueue instead of result building — corrupts BFS order.
  • Off-by-one in size - 1 - i for the right-to-left index.

Follow-up questions

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

  • Binary Tree Level Order Traversal (LC 102).
  • Vertical order traversal (LC 314).
  • Boundary of Binary Tree (LC 545).

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 pre-allocate?

Avoids the explicit reverse. Same complexity but one fewer O(level-size) pass.

Two stacks?

Alternative: one stack per direction. Pop into the other stack with children in reverse order. Same complexity, more code.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →