Leetcode - 103. Binary Tree Zigzag Level Order Traversal

🧠 Approach: BFS with Direction Flag

This is a slight variation of Level Order Traversal using BFS, with a twist:

• On even levels → add nodes left to right
• On odd levels → add nodes right to left

We keep a boolean flag leftToRight and toggle it after each level.

---

✅ Code (JavaScript):

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val === undefined ? 0 : val);
 *     this.left = (left === undefined ? null : left);
 *     this.right = (right === undefined ? null : right);
 * }
 */

/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var zigzagLevelOrder = function (root) {
  if (root === null) return [];

  const result = [];
  const queue = [root];
  let leftToRight = true;

  while (queue.length > 0) {
    const levelSize = queue.length;
    const level = [];

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();

      if (leftToRight) {
        level.push(node.val);
      } else {
        level.unshift(node.val); // Insert at front for reverse order
      }

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

    result.push(level);
    leftToRight = !leftToRight; // Toggle direction
  }

  return result;
};

---

🧮 Example:

Input Tree:

       1
      / \
     2   3
    / \   \
   4   5   6

Output:

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

---

⏱️ Time & Space Complexity

Type	Complexity
Time	O(n) — Each node is visited once
Space	O(n) — Queue and result arrays may hold all nodes in worst case

---