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.