Zigzag Level Order Traversal in DSA Javascript

Mental Model

We visit nodes level by level but alternate the direction of visiting nodes at each level.

Analogy: Imagine reading lines of text where you read the first line left to right, the second line right to left, then left to right again, like zigzagging across the page.

       1
      / \
     2   3
    / \   \
   4   5   6

Level 0: 1 (left to right)
Level 1: 3 -> 2 (right to left)
Level 2: 4 -> 5 -> 6 (left to right)

Dry Run Walkthrough

Input: Binary tree: 1 -> 2, 3 -> 4, 5, null, 6 (root 1, left 2, right 3, 2's children 4 and 5, 3's right child 6)

Goal: Traverse the tree level by level, alternating direction each level, collecting node values in zigzag order.

Step 1: Start at root level (level 0), direction left to right

Level 0: [1] -> null

Why: We begin traversal from the root node going left to right.

Step 2: Collect level 0 nodes: 1

Result so far: [[1]]

Why: First level nodes collected in left to right order.

Step 3: Move to level 1, direction right to left

Level 1: [3, 2] -> null

Why: Next level is traversed in opposite direction to zigzag.

Step 4: Collect level 1 nodes in right to left order: 3, 2

Result so far: [[1], [3, 2]]

Why: We reverse the order of nodes at this level.

Step 5: Move to level 2, direction left to right

Level 2: [4, 5, 6] -> null

Why: Direction alternates again for next level.

Step 6: Collect level 2 nodes in left to right order: 4, 5, 6

Result so far: [[1], [3, 2], [4, 5, 6]]

Why: Collect nodes in normal order at this level.

Result:

Final zigzag order: [[1], [3, 2], [4, 5, 6]]

Annotated Code

DSA Javascript

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function zigzagLevelOrder(root) {
  if (!root) return [];
  const result = [];
  const queue = [root];
  let leftToRight = true;

  while (queue.length > 0) {
    const levelSize = queue.length;
    const levelNodes = [];

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      if (leftToRight) {
        levelNodes.push(node.val); // add normally
      } else {
        levelNodes.unshift(node.val); // add reversed
      }
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }

    result.push(levelNodes);
    leftToRight = !leftToRight; // flip direction
  }

  return result;
}

// Driver code
const root = new TreeNode(1,
  new TreeNode(2, new TreeNode(4), new TreeNode(5)),
  new TreeNode(3, null, new TreeNode(6))
);

console.log(zigzagLevelOrder(root));

if (!root) return [];

handle empty tree edge case

const queue = [root];

initialize queue with root for level order traversal

while (queue.length > 0) {

process nodes level by level until none left

const levelSize = queue.length;

number of nodes at current level

for (let i = 0; i < levelSize; i++) {

iterate over all nodes in current level

const node = queue.shift();

remove node from front of queue to process

if (leftToRight) { levelNodes.push(node.val); } else { levelNodes.unshift(node.val); }

add node value in normal or reversed order depending on direction

if (node.left) queue.push(node.left); if (node.right) queue.push(node.right);

add children to queue for next level

result.push(levelNodes);

save current level's collected nodes

leftToRight = !leftToRight;

flip direction for next level

Output

[[1],[3,2],[4,5,6]]

Complexity Analysis

Time: O(n) because we visit each node exactly once during traversal

Space: O(n) because we store nodes in queue and result arrays proportional to number of nodes

vs Alternative: Compared to normal level order traversal, zigzag adds a small overhead of reversing order by unshift but still linear time overall

Edge Cases

Empty tree (root is null)

Returns empty array immediately

DSA Javascript

if (!root) return [];

Single node tree

Returns array with one level containing the single node value

DSA Javascript

const queue = [root];

Tree with only left or only right children

Traverses levels normally, zigzag order still applies but levels have single nodes

DSA Javascript

if (node.left) queue.push(node.left); if (node.right) queue.push(node.right);

When to Use This Pattern

When asked to traverse a tree level by level but with alternating directions each level, use zigzag level order traversal to collect nodes in the required order.

Common Mistakes

Mistake: Always appending nodes in the same order without reversing on alternate levels
Fix: Use unshift to add nodes at the front of the array on alternate levels to reverse order

Mistake: Modifying the queue while iterating causing incorrect level sizes
Fix: Store the current queue length before the loop to process exactly one level

Summary

Traverses a binary tree level by level, alternating the direction of node collection each level.

Use when you need to output tree nodes in zigzag or spiral order.

Flip the direction flag each level and add nodes accordingly to achieve zigzag pattern.