Zigzag Level Order Traversal in DSA Typescript - 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 given binary tree?

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[][] = [];
  let currentLevel: TreeNode[] = [root];
  let leftToRight = true;

  while (currentLevel.length > 0) {
    const levelValues: number[] = [];
    const nextLevel: TreeNode[] = [];

    for (const node of currentLevel) {
      levelValues.push(node.val);
      if (node.left) nextLevel.push(node.left);
      if (node.right) nextLevel.push(node.right);
    }

    if (!leftToRight) levelValues.reverse();
    result.push(levelValues);
    currentLevel = nextLevel;
    leftToRight = !leftToRight;
  }

  return result;
}

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

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));

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

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

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

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

💡 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, 6].

❓ Predict Output

intermediate

Zigzag traversal output for a single-node tree

What is the output of the zigzag level order traversal for a tree with only one node (value 10)?

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[][] = [];
  let currentLevel: TreeNode[] = [root];
  let leftToRight = true;

  while (currentLevel.length > 0) {
    const levelValues: number[] = [];
    const nextLevel: TreeNode[] = [];

    for (const node of currentLevel) {
      levelValues.push(node.val);
      if (node.left) nextLevel.push(node.left);
      if (node.right) nextLevel.push(node.right);
    }

    if (!leftToRight) levelValues.reverse();
    result.push(levelValues);
    currentLevel = nextLevel;
    leftToRight = !leftToRight;
  }

  return result;
}

const root = new TreeNode(10);
console.log(zigzagLevelOrder(root));

A [[10]]

B []

C [[10],[10]]

D [[0]]

💡 Hint

A single node means only one level to traverse.

The tree has only one node, so the traversal returns a single level with that node's value.

🔧 Debug

advanced

Identify the error in zigzag traversal code

What error will this code produce when run?

DSA Typescript

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

  while (currentLevel.length > 0) {
    const levelValues: number[] = [];
    const nextLevel: TreeNode[] = [];

    for (let i = currentLevel.length - 1; i >= 0; i--) {
      const node = currentLevel[i];
      levelValues.push(node.val);
      if (node.left) nextLevel.push(node.left);
      if (node.right) nextLevel.push(node.right);
    }

    if (!leftToRight) levelValues.reverse();
    result.push(levelValues);
    currentLevel = nextLevel;
    leftToRight = !leftToRight;
  }

  return result;
}

A TypeError: Cannot read property 'val' of undefined

B SyntaxError due to missing colon

C The traversal order is incorrect, but no runtime error

D Infinite loop causing timeout

💡 Hint

Check how nextLevel nodes are added when iterating backwards.

The code iterates currentLevel backwards but adds children in normal order, causing the zigzag pattern to be incorrect but no runtime error.

🧠 Conceptual

advanced

Why use two stacks in zigzag traversal?

Why is using two stacks a common approach for zigzag level order traversal?

A Because stacks allow reversing the order of nodes easily at each level

B Because stacks reduce memory usage compared to queues

C Because stacks automatically sort nodes by value

D Because stacks prevent visiting nodes multiple times

💡 Hint

Think about how to reverse the order of nodes at alternate levels.

Two stacks let us process nodes in one direction and prepare the next level in reverse order, naturally achieving zigzag traversal.

🚀 Application

expert

Zigzag traversal output for an unbalanced tree

Given the unbalanced binary tree below, what is the zigzag level order traversal output? // Tree structure: // 7 // / \ // 9 8 // \ \ // 6 5 // / / // 1 4 // \ // 3

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;
  }
}

const root = new TreeNode(7,
  new TreeNode(9, null, new TreeNode(6, new TreeNode(1), null)),
  new TreeNode(8, null, new TreeNode(5, new TreeNode(4, null, new TreeNode(3)), null))
);

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

  while (currentLevel.length > 0) {
    const levelValues: number[] = [];
    const nextLevel: TreeNode[] = [];

    for (const node of currentLevel) {
      levelValues.push(node.val);
      if (node.left) nextLevel.push(node.left);
      if (node.right) nextLevel.push(node.right);
    }

    if (!leftToRight) levelValues.reverse();
    result.push(levelValues);
    currentLevel = nextLevel;
    leftToRight = !leftToRight;
  }

  return result;
}

console.log(zigzagLevelOrder(root));

A [[7],[9,8],[5,6],[1,4],[3]]

B [[7],[8,9],[6,5],[4,1],[3]]

C [[7],[8,9],[5,6],[4,1],[3]]

D [[7],[9,8],[6,5],[1,4],[3]]

💡 Hint

Follow the zigzag pattern carefully level by level.

Level 0 left to right: [7] Level 1 right to left: [8,9] Level 2 left to right: [6,5] Level 3 right to left: [4,1] Level 4 left to right: [3]