Given the root of a binary tree, display the values of its nodes while performing a level order traversal. Return the node values for all levels in a string separated by the character :. If the tree is empty, i.e., the number of nodes is 0 0 , then return “None” as the output.

level-order-traversal.js

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

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

export let levelOrderTraversal = function (root) {
  if (!root) {
    return "None";
  }
  const values = [[]];
  const queue = [[root, 0]];

  while (queue.length > 0) {
    const [node, level] = queue.shift();
    if (values[level] == null) {
      values[level] = [];
    }
    values[level].push(node.data);
    if (node.left) {
      queue.push([node.left, level + 1]);
    }
    if (node.right) {
      queue.push([node.right, level + 1]);
    }
  }

  return values.map((level) => level.join(", ")).join(" : ");
};

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