BinaryTreeVerticalOrder

BinaryTreeVerticalOrder.js

class Node {
  constructor(val = 0, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

const root = new Node(6)
root.left = new Node(3)
root.left.left = new Node(2)
root.left.right = new Node(5)
root.right = new Node(7)
root.right.right = new Node(9)


function verticalOrder(root) {
  if (!root) return [];

  const verticalMap = new Map(); // Using Map to maintain insertion order
  const queue = [{ node: root, distance: 0 }];
  let minDist = 0
  let maxDist = 0

  while (queue.length) {
    const { node, distance } = queue.shift();

    if (!verticalMap.has(distance)) {
      verticalMap.set(distance, []);
    }
    verticalMap.get(distance).push(node.val);

    minDist = Math.min(minDist, distance)
    maxDist = Math.max(maxDist, distance)

    if (node.left) {
      queue.push({ node: node.left, distance: distance - 1 });
    }
    if (node.right) {
      queue.push({ node: node.right, distance: distance + 1 });
    }
  }

  const result = []
  for (let i = minDist; i <= maxDist; i++) {
    result.push(verticalMap.get(i))
  }
  return result;
}

//[ [ 2 ], [ 3 ], [ 6, 5 ], [ 7 ], [ 9 ] ]
console.log(verticalOrder(root));