Zigzag Level Order Traversal in DSA Typescript

Mental Model

We visit nodes level by level, but switch direction each level, going left to right then right to left alternately.

Analogy: Imagine reading lines of text where the first line you read left to right, the next 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 as root, 2 and 3 as children of 1, 4 and 5 as children of 2, 6 as right child of 3

Goal: Traverse the tree level by level, but alternate direction each level to get zigzag order

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

Level 0: [1]
Output: [[1]]

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

Step 2: Move to level 1, switch direction to right to left

Level 1 nodes: 2, 3
Output: [[1], [3, 2]]

Why: We reverse order at this level to get zigzag pattern

Step 3: Move to level 2, switch direction back to left to right

Level 2 nodes: 4, 5, 6
Output: [[1], [3, 2], [4, 5, 6]]

Why: Direction alternates again to left to right

Result:

Final output: [[1], [3, 2], [4, 5, 6]]

Annotated Code

DSA Typescript

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

function zigzagLevelOrder(root: TreeNode | null): number[][] {
  if (!root) return [];
  const result: number[][] = [];
  const queue: TreeNode[] = [root];
  let leftToRight = true;

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

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!; // remove front node
      // Add node value based on current direction
      if (leftToRight) {
        levelNodes.push(node.val); // left to right
      } else {
        levelNodes.unshift(node.val); // right to left
      }
      // Add children for next level
      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 to test
const root = new TreeNode(1,
  new TreeNode(2, new TreeNode(4), new TreeNode(5)),
  new TreeNode(3, null, new TreeNode(6))
);
const output = zigzagLevelOrder(root);
console.log(JSON.stringify(output));

if (!root) return [];

handle empty tree edge case

const queue: TreeNode[] = [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;

determine number of nodes at current level

const node = queue.shift()!;

remove front node to process current level

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

add node value in correct order based on direction

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

enqueue children for next level

leftToRight = !leftToRight;

flip direction for next level

Output

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

Complexity Analysis

Time: O(n) because each node is visited exactly once during traversal

Space: O(n) because the queue and result store nodes and values for each level

vs Alternative: Compared to normal level order traversal, zigzag adds a small overhead for reversing order but still remains O(n)

Edge Cases

empty tree (root is null)

returns empty array immediately

DSA Typescript

if (!root) return [];

tree with single node

returns array with one level containing that node

DSA Typescript

const queue: TreeNode[] = [root];

tree with only left or only right children

still traverses levels correctly alternating direction

DSA Typescript

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

When to Use This Pattern

When a problem asks for level order traversal but with alternating directions each level, use zigzag level order traversal to handle the direction switch cleanly.

Common Mistakes

Mistake: Always appending node values left to right without reversing on alternate levels
Fix: Use unshift to add values at front on alternate levels to reverse order

Mistake: Reversing the entire level array after collecting all nodes instead of inserting in correct order
Fix: Insert nodes in correct order during traversal to avoid extra reversal step

Summary

Traverses a binary tree level by level, alternating direction each level to create a zigzag pattern.

Use when you need to visit nodes in a breadth-first manner but want to alternate the order of nodes at each level.

The key insight is to switch the order of inserting node values at each level instead of reversing after traversal.

Practice

1. What is the main idea behind Zigzag Level Order Traversal of a binary tree?

easy

A. Traverse the tree only from right to left at all levels

B. Traverse the tree only from left to right at all levels

C. Traverse each level of the tree alternating between left-to-right and right-to-left order

D. Traverse nodes in random order without level consideration

Solution

1. Step 1: Understand level order traversal

   Normal level order traversal visits nodes level by level from left to right.

2. Step 2: Identify zigzag pattern

   Zigzag traversal alternates direction each level: left-to-right, then right-to-left, and so on.

3. Final Answer:

   Traverse each level of the tree alternating between left-to-right and right-to-left order -> Option C

4. Quick Check:

   Zigzag means alternating directions [OK]

Hint: Remember zigzag means switching direction each level [OK]

Common Mistakes:

• Thinking traversal is always left to right
• Confusing zigzag with normal level order
• Ignoring level-by-level traversal

2. Which of the following TypeScript code snippets correctly initializes a queue for level order traversal?

easy

A. const queue = {}; queue.enqueue(root);

B. const queue = new Set<TreeNode>(); queue.add(root);

C. const queue: TreeNode[] = new TreeNode(); queue.push(root);

D. const queue: TreeNode[] = []; queue.push(root);

Solution

1. Step 1: Identify correct queue initialization

   In TypeScript, an array can be used as a queue with push and shift methods.

2. Step 2: Check each option

   const queue: TreeNode[] = []; queue.push(root); correctly declares an array and pushes root node. Others use wrong types or methods.

3. Final Answer:

   const queue: TreeNode[] = []; queue.push(root); -> Option D

4. Quick Check:

   Array with push is correct queue usage [OK]

Hint: Use array push/shift for queue in TypeScript [OK]

Common Mistakes:

• Using Set instead of queue
• Incorrect object initialization
• Using non-existent enqueue method

3. What is the output of the zigzag level order traversal for the binary tree below?

    1
   / \
  2   3
 / \   \
4   5   6

medium

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

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

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

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

Solution

1. Step 1: Traverse level 0 left to right

   Level 0 has node 1, so output is [1].

2. Step 2: Traverse level 1 right to left

   Level 1 nodes are 2 and 3; reversed order is [3, 2].

3. Step 3: Traverse level 2 left to right

   Level 2 nodes are 4, 5, 6; order is [4, 5, 6].

4. Final Answer:

   [[1], [3, 2], [4, 5, 6]] -> Option A

5. Quick Check:

   Zigzag alternates direction each level [OK]

Hint: Alternate direction each level starting left-to-right [OK]

Common Mistakes:

• Not reversing nodes on odd levels
• Mixing node order at last level
• Confusing left and right children order

4. Consider this TypeScript code snippet for zigzag traversal. What is the bug?

const result: number[][] = [];
const queue: TreeNode[] = [root];
let leftToRight = true;
while (queue.length > 0) {
  const levelSize = queue.length;
  const levelNodes: number[] = [];
  for (let i = 0; i < levelSize; i++) {
    const node = queue.shift()!;
    if (leftToRight) levelNodes.push(node.val);
    else levelNodes.unshift(node.val);
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
  result.push(levelNodes);
  // Missing toggle of leftToRight
}

medium

A. Children nodes are pushed in wrong order

B. leftToRight is never toggled, so traversal direction never changes

C. levelNodes.unshift() should be levelNodes.push() always

D. queue.shift() is used instead of queue.pop() causing wrong order

Solution

1. Step 1: Check direction toggle

   The variable leftToRight controls direction but is never changed inside the loop.

2. Step 2: Understand effect of missing toggle

   Without toggling, direction stays same, so zigzag pattern breaks.

3. Final Answer:

   leftToRight is never toggled, so traversal direction never changes -> Option B

4. Quick Check:

   Toggle direction each level for zigzag [OK]

Hint: Toggle direction flag after each level [OK]

Common Mistakes:

• Forgetting to toggle leftToRight
• Using wrong queue methods
• Incorrectly adding nodes to level array

5. Given a binary tree, how would you modify the zigzag level order traversal to return a flat array of node values in zigzag order instead of nested arrays per level?

hard

A. Concatenate each level's nodes to a single array instead of pushing nested arrays

B. Use a stack instead of a queue for traversal

C. Traverse all nodes left to right ignoring zigzag

D. Return only the last level's nodes

Solution

1. Step 1: Understand current output format

   Zigzag traversal usually returns nested arrays, one per level.

2. Step 2: Modify to flat array

   Instead of pushing level arrays, append each level's nodes to a single result array.

3. Step 3: Keep zigzag order

   Maintain alternating direction logic while flattening output.

4. Final Answer:

   Concatenate each level's nodes to a single array instead of pushing nested arrays -> Option A

5. Quick Check:

   Flatten by concatenation, keep zigzag order [OK]

Hint: Append levels to one array instead of nested arrays [OK]

Common Mistakes:

• Changing traversal order incorrectly
• Using stack breaks level order
• Returning only partial nodes