binary_search_tree.js

/**
 * Binary Search Tree
 *
 * This is a tree data structure that orders the nodes of the tree such that:
 * - The left subtree only contains nodes of lesser values
 * - The right subtree only contains nodes of greater values
 * - There are no duplicate nodes
 *
 * What this is good for:
 * - Storing unique values
 * - Fast searching, insertion
 * - Implementing Sets, Multisets, Maps
 *
 * References:
 * https://en.wikipedia.org/wiki/Binary_search_tree
 * https://en.wikipedia.org/wiki/In-order_traversal
 */

function BinarySearchTree() {
  this.root = undefined;
}

/**
 * Search the tree for a value
 * @param {Number} value
 * @param {Node} start - optionally start search from another node
 * @returns {Node} - node from tree if it is found, otherwise undefined
 */
BinarySearchTree.prototype.search = function(value, start) {
  var node = start || this.root;
  while (node) {
    if (value < node.value) {
      node = node.left;
    } else if (value > node.value) {
      node = node.right;
    } else if (node.value === value) {
      break;
    }
  }
  return node;
};

/**
 * Iterate through all the nodes of a subtree beginning at specified node
 * @param {Function} fn - callback function to be applied to each node
 * @param {String} order - optionally traverse the tree in alternative orders
 */
BinarySearchTree.prototype.traverse = function(node, fn, order) {
  var traversals = {
    // depth-first in-order traversal (min value node -> max value node)
    inOrder: function(node, visit) {
      if (! node) return;
      traversals.inOrder(node.left, visit);
      visit(node);
      traversals.inOrder(node.right, visit);
    },

    // depth-first pre-order traversal (root node -> min node -> max node)
    preOrder: function(node, visit) {
      if (! node) return;
      visit(node);
      traversals.preOrder(node.left, visit);
      traversals.preOrder(node.right, visit);
    },

    // depth-first post-order traversal (deepest min node -> root node)
    postOrder: function(node, visit) {
      if (! node) return;
      traversals.postOrder(node.left, visit);
      traversals.postOrder(node.right, visit);
      visit(node);
    }
  };
  var traverseOrder = order || 'inOrder';
  return traversals[traverseOrder](node, fn);
};

/**
 * Iterate through all the nodes of the tree and apply a function.
 * @param {Function} fn - callback function to be applied to each node
 * @param {String} order - optionally traverse the tree in alternative orders
 * @returns {BinarySearchTree} - this
 */
BinarySearchTree.prototype.each = function(fn, order) {
  this.traverse(this.root, fn, order);
  return this;
};

/**
 * Traverse the tree and count the nodes.
 * @returns {Number} - count of the nodes in the tree
 */
BinarySearchTree.prototype.size = function() {
  var count = 0;
  this.each(function(node) { count++; });
  return count;
};

/**
 * Inserts a new node into the tree if it does not already exist
 * @param {Number} value - new value to be inserted into tree
 * @returns {BinarySearchTree} - this
 */
BinarySearchTree.prototype.insert = function(value) {
  if (! this.root) {
    this.root = new Node(value); // Set root node if it is not defined
  } else {
    var node = this.root;
    while (node) {
      if (value < node.value) {
        if (! node.left) node.left = new Node(value);
        node = node.left;
      } else if (value > node.value) {
        if (! node.right) node.right = new Node(value);
        node = node.right;
      } else {
        break;
      }
    }
  }
  return this;
};

/**
 * Remove a value from the tree
 * @returns {BinarySearchTree} - this
 */
BinarySearchTree.prototype.remove = function(value) {
  // TODO: this is basically a duplicated search, refactor this
  var node = this.root;
  var parent;
  while (node) {
    if (value < node.value) {
      parent = node;
      node = node.left;
    } else if (value > node.value) {
      parent = node;
      node = node.right;
    } else if (node.value === value) {
      break;
    }
  }

  if (node) {
    if (node.left && node.right) {
      // Deleting a node with two children
      if (node.left < node.right ) {
        node.value = node.left.value;
        return this.remove(node.value);
      } else {
        node.value = node.right.value;
        return this.remove(node.value);
      }

    } else if (node.left || node.right) {
      // Deleting node with one child, replace node with child
      var child = node.left || node.right;
      if (parent.left == node) {
        parent.left = child;
      } else {
        parent.right = child;
      }
    } else {
      // Delete leaf node with no children, remove references to node
      if (parent.left == node) {
        parent.left = undefined;
      } else {
        parent.right = undefined;
      }
    }
  }
  return this;
};


/**
 * Traverse the tree 'in-order' and return all the nodes in order visited
 * @returns {Array} - array of Node objects
 */
BinarySearchTree.prototype.sort = function(node) {
  var sorted = [];
  this.traverse(this.root, function(node) { sorted.push(node); });
  return sorted;
};

/**
 * Finds the smallest value node in the tree - the left-most node.
 * @returns {Node}
 */
BinarySearchTree.prototype.min = function() {
  var min = this.root;
  while (min.left) min = min.left;
  return min;
};

/**
 * Finds the greatest value node in the tree - the right-most node.
 * @returns {Node}
 */
BinarySearchTree.prototype.max = function() {
  var max = this.root;
  while (max.right) max = max.right;
  return max;
};

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

module.exports = BinarySearchTree;