Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumtree-bfs

Binary Tree Zigzag Level Order Traversal

Problem (restated)

Level-order values, but alternate left→right and right→left each level.

Intuition

BFS levels; reverse odd levels (or use deque direction).

Approaches

Level BFS + reverse

Unverified

Time O(n)Space O(w)

Idea. collect level as usual; if depth odd reverse before push.

Walkthrough. [3,9,20,null,null,15,7] → [[3],[20,9],[15,7]].

Trade-offs. Deque insert-front is optional sugar; reverse is clear.

Solution

export class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

export function zigzagLevelOrder(root: TreeNode | null): number[][] {
  if (!root) return [];
  const res: number[][] = [];
  const q: TreeNode[] = [root];
  let leftToRight = true;
  while (q.length) {
    const size = q.length;
    const level: number[] = [];
    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();
    res.push(level);
    leftToRight = !leftToRight;
  }
  return res;
}

export class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

export function zigzagLevelOrder(root: TreeNode | null): number[][] {
  if (!root) return [];
  const res: number[][] = [];
  const q: TreeNode[] = [root];
  let leftToRight = true;
  while (q.length) {
    const size = q.length;
    const level: number[] = [];
    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();
    res.push(level);
    leftToRight = !leftToRight;
  }
  return res;
}

Template connection

Tree BFS with level post-process.

Reflection

Level BFS stays the same. Reverse each odd level’s list to get the zigzag.
Always enqueue left to right. The reverse applies only to that level’s output.
One node shows no reverse. A skewed tree has one node on every row.