Binary Search Tree

Like other trees (well, not leafy ones), a binary search tree is a data structure made up of nodes that contain a value and references to child nodes. Unlike more basic tree structures, there are two characteristics of a binary search tree that make it uniquely useful for storing and searching data: (1) each node can have a maximum of two children - hence, binary search tree, and (2) of these two children, the left child has a value less than the value of the parent, and the right child has a value greater than the value of the parent.

When searching a BST for a particular value, you begin at the root node and travel left or right until you either find the target value or reach the end of the tree. Searching for a value in a binary search tree has a lesser time complexity than simply searching through an array because rather than iterating over every possible value(O-n), you recursively eliminate a subset of possible values at every step- in the best possible scenario, when the tree is perfectly balanced, you eliminate half of the possibilities on every iteration (O-logn).

Here is my javascript implementation for building a searching a binary search tree:

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

var BinarySearchTree = function(value) {  
  this.root = Node(value);
};

BinarySearchTree.prototype.insert = function(value, parent) {  
  var parent = parent || this.root;
  var node = new Node(value);

  if (parent.value > value) {
    if (!parent.left) {
      parent.left = node;
    } else {
      this.insert(value, parent.left);
    }
  } else if (parent.value < value) {
    if (!parent.right) {
      parent.right = node;
    } else {
      this.insert(value, parent.right)
    }
  }
};

BinarySearchTree.prototype.contains = function(target, item) {  
  var item = item || this.root;
  if (item.value === target) {
    return true;
  } else if (item.value > target && item.left) {
    return this.contains(target, item.left);
  } else if (item.value < target && item.right) {
    return this.contains(target, item.right);
  }
  return false;
};

Because data is being sorted as it is added to the BST, it is easy to recursively collapse a BST into a sorted array (if you want to):

binarySearchTree.collapseTree = function(node) {  
  node = node || root;
  var result = [node.value];
  if (node.left) {
    result = this.collapseTree(node.left).concat(result);
  }
  if (node.right) {
    result = result.concat(this.collapseTree(node.right));
  }
    return result;
}