Zigzag Level Order Traversal in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the queue with the root node for level order traversal.

DSA Typescript

const queue: TreeNode[] = [[1]];

Drag options to blanks, or click blank then click option'

Aundefined

Bnull

C[]

Droot

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing queue with null or empty array instead of root node.

We start the traversal by adding the root node to the queue.

2fill in blank

medium

Complete the code to toggle the direction of traversal after each level.

DSA Typescript

leftToRight = ![1];

Drag options to blanks, or click blank then click option'

Aqueue

BleftToRight

ClevelNodes

Dresult

Attempts:

3 left

💡 Hint

Common Mistakes

Trying to toggle the wrong variable or using assignment instead of negation.

We flip the boolean leftToRight to change the traversal direction for the next level.

3fill in blank

hard

Fix the error in the code that reverses the level nodes when traversing right to left.

DSA Typescript

if (!leftToRight) levelNodes.[1]();

Drag options to blanks, or click blank then click option'

Apop

Bsort

Creverse

Dshift

Attempts:

3 left

💡 Hint

Common Mistakes

Using sort() which sorts alphabetically or numerically, not reversing.

Using pop() or shift() which remove elements instead of reversing.

We use reverse() to flip the order of nodes for right-to-left traversal.

4fill in blank

hard

Fill both blanks to correctly add child nodes to the queue for the next level.

DSA Typescript

if (node.[1]) queue.push(node.[2]);

Drag options to blanks, or click blank then click option'

Aleft

Bright

Cparent

Dchild

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing left and right properties incorrectly.

Using non-existent properties like parent or child.

We check if the left child exists and then add it to the queue.

5fill in blank

hard

Fill all three blanks to correctly add the right child node to the queue if it exists.

DSA Typescript

if (node.[1]) queue.[2](node.[3]);

Drag options to blanks, or click blank then click option'

Aleft

Bpush

Cright

Dpop

Attempts:

3 left

💡 Hint

Common Mistakes

Using left instead of right for the child node.

Using pop instead of push to add nodes.

We check if the right child exists and then push it to the queue.

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