breadth_first_search.js

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

  getChildren() {
    let children = []
    if (this.left) {
      children.push(this.left)
    }
    if (this.right) {
      children.push(this.right)
    }
    return children
  }
}

class BinarySearchTree {

  constructor() {
    this.root = null;
  }

  insertNode(val) {

    var node = new Node(val)

    var currentNode;

    if (!this.root) {
      this.root = node;
    } else {
      currentNode = this.root;
      while (currentNode) {
        if (val < currentNode.data) {
          if (!currentNode.left) {
            currentNode.left = node;
            break;
          } else {
            currentNode = currentNode.left;
          }
        } else if (val > currentNode.data) {
          if (!currentNode.right) {
            currentNode.right = node;
            break;
          } else {
            currentNode = currentNode.right;
          }
        } else {
          console.log('Ignoring this value as the BST supposed to be a tree containing UNIQUE values');
          break;
        }
      }
    }
  }

}

function breadthFirstSearch(tree, MAX_DEPTH = null) {
  let nodes = [] // list of nodes
  let queue = [] // remember visited nodes
  let depth = 0

  queue.push(tree.root) // start queue with root

  let level_children_count = null
  let children_found = 0
  let next_level_children_count = 0

  while (queue.length !== 0) {
    const POSITION = queue.shift()
    const CHILDREN = POSITION.getChildren()
    if (level_children_count === null) {
      level_children_count = CHILDREN.length
    }

    CHILDREN.forEach(node => {
      children_found++

      const NODE_CHILDREN = node.getChildren().length
      next_level_children_count += NODE_CHILDREN

      if (Array.isArray(nodes[depth])) {
        nodes[depth].push(node.data) // if node already in this level then add
      } else {
        nodes[depth] = [node.data] // first node in this level so create array
      }

      if (NODE_CHILDREN > 0) {
        queue.push(node)
      }
    });

    if (children_found == level_children_count) {
      depth++
      level_children_count = next_level_children_count
      children_found = 0
      next_level_children_count = 0
      if (depth == MAX_DEPTH) {
        break; // exit while loop since we reached MAX_DEPTH
      }
    }
  }

  return nodes
}

var BST = new BinarySearchTree();

BST.insertNode(8);
BST.insertNode(3);
BST.insertNode(10);
BST.insertNode(1);
BST.insertNode(6);
BST.insertNode(14);
BST.insertNode(4);
BST.insertNode(7);
BST.insertNode(13);

let nodes = breadthFirstSearch(BST)
console.log(nodes) // [ [ 3, 10 ], [ 1, 6, 14 ], [ 4, 7, 13 ] ]

// return values from last level
const LAST_LEVEL = nodes.length - 1
console.log(nodes[LAST_LEVEL].join(",")) // 4,7,13


let nodes_with_max_depth = breadthFirstSearch(BST, MAX_DEPTH = 2)
console.log(nodes_with_max_depth) // [ [ 3, 10 ], [ 1, 6, 14 ] ]

// return values from last level of MAX_DEPTH 2
const LAST_LEVEL_WITH_MAX_DEPTH = nodes_with_max_depth.length - 1
console.log(nodes_with_max_depth[LAST_LEVEL_WITH_MAX_DEPTH].join(",")) // 1,6,14