Given a binary tree, return its zigzag level order traversal. The zigzag level order traversal corresponds to traversing nodes from left to right for one level, and then right to left for the next level, and so on, reversing direction after every level.

binary-tree-zigzag-order.js

import { TreeNode } from "./ds_v1/BinaryTree.js";

// Definition of a binary tree node
// class TreeNode {
//   constructor(data) {
//     this.data = data;
//     this.left = null;
//     this.right = null;
//   }
// }

function zigzagLevelOrder(root) {
  if (!root) {
    return [];
  }
  const dq = [root];
  const result = [];
  let reverse = false;

  while (dq.length > 0) {
    // at each iteration of the while loop we empty the deque
    // making sure we are processing the whole level before moving to the next
    result.push([]);
    const size = dq.length;
    for (let i = 0; i < size; ++i) {
      if (reverse) {
        const node = dq.pop();
        result[result.length - 1].push(node.data);
        if (node.right) {
          dq.unshift(node.right);
        }
        if (node.left) {
          dq.unshift(node.left);
        }
      } else {
        const node = dq.shift();
        result[result.length - 1].push(node.data);
        if (node.left) {
          dq.push(node.left);
        }
        if (node.right) {
          dq.push(node.right);
        }
      }
    }
    reverse = !reverse;
  }

  // Replace this placeholder return statement with your code
  return result;
}

export { zigzagLevelOrder };

// tc: O(n)
// sc: O(n)