Skip to main content

75. Binary Tree Zigzag Level Order Traversal

mediumAsked at Ola

Return the zigzag level-order traversal of a binary tree.

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

Problem

Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. Even levels go left-to-right; odd levels right-to-left.

Constraints

  • Number of nodes is in [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 = []
Output
[]

Approaches

1. Level then reverse

Compute normal level order; reverse every other level.

Time
O(n)
Space
O(n)
// reuse levelOrder then for odd i, level.reverse()

Tradeoff:

2. BFS with direction flag

Push to either front or back of the current level array based on direction.

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

Tradeoff:

Ola-specific tips

Ola interviewers ask the direction-flag variant; tie it to alternating broadcast direction across left/right zone children to balance fanout.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →