Breadth first search binary search tree javascript implementation

Question

I have the following code that implements a BST tree in JavaScript.

function Node(value) {
  this.left = null;
  this.right = null;
  this.value = value;
}

function BinarySearchTree() {
  this.root = null;
  return;
}

BinarySearchTree.prototype.push = function(value) {

  if (!this.root) {
    this.root = new Node(value);
    return;
  }

  var currentRoot = this.root;
  var newNode = new Node(value);
  while (currentRoot) {
    if (value < currentRoot.value) {
      if (!currentRoot.left) {
        currentRoot.left = newNode;
        break;
      } else {
        currentRoot = currentRoot.left;
      }
    } else {

      if (!currentRoot.right) {
        currentRoot.right = newNode;
        break;
      } else {
        currentRoot = currentRoot.right;
      }

    }

  }

}

var a = new BinarySearchTree();
a.push(27);
a.push(14);
a.push(35);
a.push(10);
a.push(19);
a.push(31);
a.push(42);

I am trying to implement a function which can do a breadth first traversal of the tree. This is what I have tried so far.

console.log(a.root.value);
traverse(a.root);

//function to traverse 
function traverse(node) {

  currentNode = node;
  while (currentNode.left) {
    displayNodes(currentNode);
    parent = currentNode;
    currentNode = currentNode.left;
    displayNodes(currentNode);
    if(parent.right!=null){
    displayNodes(parent.right);
    }
  }
}

//function that displays the left and right node of a node 
function displayNodes(node) {


  if (node.left != null) {
    console.log(node.left.value);
  }
  if (node.right != null) {
    console.log(node.right.value);
  }
}

I am unable to implement a function that could scale with a large number of data. I am not sure if a recursive method to traverse would be better or using a while loop. How can I implement the function? I know that the function gives unexpected behavior? What correction should I make?

Answer 1

You currently traverse the path from the root node to the left-most leaf.

A simple non-recursive breadth-first traversal function invoking a callback on each traversed node could look as follows:

// Breadth-first traversal:
function traverse(node, cb) {
  var current = [node];
  while (current.length > 0) {
    var next = [];
    for (var node of current) {
      cb(node);
      if (node.left) next.push(node.left);
      if (node.right) next.push(node.right);
    }
    current = next;
  }
}

// Example:
traverse(root, function(node) {
  console.log(node.value);
});

It works by keeping an array of already discovered or traversed nodes current which initially contains just your root node. Now, you iteratively replace each node in that list with its children. In above function, the children are stored in a next array. At the end of each iteration, all nodes of the current level in current are replaced with all their children of the next deeper level in next. See also the first suggestion given by @DavidKnipe's answer.

A non-recursive approach has the advantage of not being subject to the call stack size limit. This theoretically allows you to handle larger data structures when the call stack size is limited.