Zigzag Level Order Traversal in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Zigzag Level Order Traversal on a simple tree

What is the output of the zigzag level order traversal for the following binary tree?

Tree structure:
1
/ \
2 3
/ \
4 5

DSA Javascript

function zigzagLevelOrder(root) {
  if (!root) return [];
  const result = [];
  const queue = [root];
  let leftToRight = true;
  while (queue.length) {
    const levelSize = queue.length;
    const levelNodes = [];
    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);
    leftToRight = !leftToRight;
  }
  return result;
}

// Tree nodes
const root = { val: 1, left: { val: 2, left: { val: 4, left: null, right: null }, right: null }, right: { val: 3, left: null, right: { val: 5, left: null, right: null } } };
console.log(zigzagLevelOrder(root));

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

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

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

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

💡 Hint

Remember that the traversal direction alternates at each level.

The traversal starts left to right at level 0: [1]. Then right to left at level 1: [3, 2]. Then left to right at level 2: [4, 5].

🧠 Conceptual

intermediate

Understanding the zigzag traversal direction toggle

In zigzag level order traversal, why do we toggle the direction of traversal after each level?

A To prioritize visiting leaf nodes before internal nodes.

B To visit all nodes in the tree in ascending order of their values.

C To ensure nodes are visited in a spiral pattern alternating left-to-right and right-to-left at each level.

D To reduce the time complexity of the traversal.

💡 Hint

Think about the pattern the traversal creates visually.

Toggling direction creates a zigzag or spiral pattern, alternating the order nodes are visited at each level.

🔧 Debug

advanced

Identify the error in this zigzag traversal implementation

What error does the following code produce when run on a non-empty binary tree?

DSA Javascript

function zigzagLevelOrder(root) {
  if (!root) return [];
  const result = [];
  const queue = [root];
  let leftToRight = true;
  while (queue.length) {
    const levelSize = queue.length;
    const levelNodes = [];
    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);
    leftToRight = !leftToRight;
  }
  return result;
}

A SyntaxError: Unexpected token

B TypeError: Cannot read property 'val' of undefined

C Infinite loop causing program to hang

D No error, outputs correct zigzag traversal

💡 Hint

Check the loop boundary condition in the for loop.

The for loop uses i <= levelSize, which causes one extra iteration where queue.shift() returns undefined, leading to accessing 'val' of undefined.

❓ Predict Output

advanced

Output of zigzag traversal on a larger tree

What is the output of the zigzag level order traversal for this tree?

Tree structure:
10
/ \
6 15
/ \ \
3 8 20
/ / \
7 17 25

DSA Javascript

function zigzagLevelOrder(root) {
  if (!root) return [];
  const result = [];
  const queue = [root];
  let leftToRight = true;
  while (queue.length) {
    const levelSize = queue.length;
    const levelNodes = [];
    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);
    leftToRight = !leftToRight;
  }
  return result;
}

const root = {
  val: 10,
  left: {
    val: 6,
    left: { val: 3, left: null, right: null },
    right: { val: 8, left: { val: 7, left: null, right: null }, right: null }
  },
  right: {
    val: 15,
    left: null,
    right: {
      val: 20,
      left: { val: 17, left: null, right: null },
      right: { val: 25, left: null, right: null }
    }
  }
};
console.log(zigzagLevelOrder(root));

A [[10],[15,6],[3,8,20],[25,17,7]]

B [[10],[15,6],[3,8,20],[7,17,25]]

C [[10],[6,15],[20,8,3],[7,17,25]]

D [[10],[6,15],[3,8,20],[7,17,25]]

💡 Hint

Remember the direction alternates each level starting left to right.

Level 0: left to right [10]
Level 1: right to left [15,6]
Level 2: left to right [3,8,20]
Level 3: right to left [25,17,7]

🧠 Conceptual

expert

Why use unshift for right-to-left insertion in zigzag traversal?

In the zigzag level order traversal, why do we use unshift to add node values when traversing right to left instead of push?

A Because push would cause nodes to be visited twice.

B Because unshift is faster than push for arrays in JavaScript.

C Because unshift removes duplicates automatically.

D Because unshift inserts elements at the beginning, reversing the order of nodes at that level.

💡 Hint

Think about how the order of nodes at a level is reversed.

Using unshift inserts each node value at the front of the array, reversing the order of nodes collected at that level to achieve right-to-left order.

Practice

1. What is the main difference between a normal level order traversal and a zigzag level order traversal of a binary tree?

easy

A. Zigzag traversal visits nodes only on even levels.

B. Zigzag traversal alternates the direction of node visits at each level.

C. Zigzag traversal visits nodes in reverse order at all levels.

D. Zigzag traversal skips leaf nodes.

Solution

1. Step 1: Understand normal level order traversal

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

2. Step 2: Understand zigzag traversal difference

   Zigzag traversal alternates direction: left to right on one level, then right to left on the next, and so on.

3. Final Answer:

   Zigzag traversal alternates the direction of node visits at each level. -> Option B

4. Quick Check:

   Zigzag = alternate directions [OK]

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

Common Mistakes:

• Thinking zigzag skips levels
• Assuming zigzag always reverses order
• Confusing zigzag with normal level order

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

easy

A. const queue = new Set(); queue.add(root);

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

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

D. const queue = new Map(); queue.set(root);

Solution

1. Step 1: Identify correct queue initialization in JavaScript

   JavaScript arrays can be used as queues with push and shift methods.

2. Step 2: Check each option

   const queue = []; queue.push(root); uses an array and push method correctly. Options B, C, and D use incorrect data structures or methods for queue behavior.

3. Final Answer:

   const queue = []; queue.push(root); -> Option C

4. Quick Check:

   Array with push = queue [OK]

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

Common Mistakes:

• Using Set or Map instead of array for queue
• Using non-existent enqueue method
• Initializing queue as an object

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 nodes: [1]

2. Step 2: Traverse level 1 right to left

   Level 1 nodes: [2, 3] reversed to [3, 2]

3. Step 3: Traverse level 2 left to right

   Level 2 nodes: [4, 5, 6]

4. Final Answer:

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

5. Quick Check:

   Zigzag levels alternate direction [OK]

Hint: Alternate direction each level, start left to right [OK]

Common Mistakes:

• Not reversing the order on odd levels
• Reversing all levels
• Mixing node values order

4. Consider this snippet for zigzag traversal:

while(queue.length) {
  let levelSize = queue.length;
  let levelNodes = [];
  for(let i = 0; i < levelSize; i++) {
    let node = queue.shift();
    levelNodes.push(node.val);
    if(node.left) queue.push(node.left);
    if(node.right) queue.push(node.right);
  }
  if(reverse) levelNodes.reverse();
  result.push(levelNodes);
  reverse = !reverse;
}

What is the bug in this code?

medium

A. The variable 'reverse' is not initialized before the loop.

B. Using queue.shift() causes runtime error.

C. levelNodes.reverse() should be called before pushing nodes.

D. Children nodes should be pushed after reversing levelNodes.

Solution

1. Step 1: Check variable initialization

   The variable 'reverse' is used but not declared or initialized before the loop, causing a ReferenceError.

2. Step 2: Verify other code parts

   queue.shift() is valid for arrays, reversing after collecting nodes is correct, and pushing children before reversing is standard.

3. Final Answer:

   The variable 'reverse' is not initialized before the loop. -> Option A

4. Quick Check:

   Uninitialized variable 'reverse' causes error [OK]

Hint: Always initialize flags before loops [OK]

Common Mistakes:

• Assuming shift() is invalid
• Reversing nodes before collecting children
• Pushing children after reversing level nodes

5. You want to implement zigzag level order traversal but optimize space by avoiding reversing arrays. Which approach below correctly achieves this?

hard

A. Use a deque and insert nodes at front or back depending on direction.

B. Use a queue and reverse the entire result array at the end.

C. Use recursion and collect nodes in normal order only.

D. Use two stacks, one for current level and one for next level, alternating push order.

Solution

1. Step 1: Understand reversing avoidance

   Reversing arrays costs extra time and space; using two stacks can avoid this by controlling push order.

2. Step 2: Analyze options

   Use two stacks, one for current level and one for next level, alternating push order. uses two stacks and alternates push order to get zigzag without reversing. Use a deque and insert nodes at front or back depending on direction. needs a deque which is not native in JS. Use a queue and reverse the entire result array at the end. reverses at the end, not avoiding reversing. Use recursion and collect nodes in normal order only. does not handle zigzag properly.

3. Final Answer:

   Use two stacks, one for current level and one for next level, alternating push order. -> Option D

4. Quick Check:

   Two stacks alternate push order = no reverse [OK]

Hint: Two stacks alternate push order to avoid reversing [OK]

Common Mistakes:

• Using queue and reversing result at end
• Trying recursion without direction control
• Assuming deque is native in JavaScript