Binary Search Tree (BST)

Definition

A binary search tree (BST), sometimes also called an ordered or sorted binary tree, is a node-based binary tree data structure which has the following properties:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• The left and right subtree each must also be a binary search tree.
• There must be no duplicate nodes.

Source: Wikipedia

Code: https://github.com/felipernb/algorithms.js/blob/master/src/data_structures/bst.js

Tests: https://github.com/felipernb/algorithms.js/blob/master/test/data_structures/bst.js

How to use

Import

var BST = require('algorithms').DataStructure.BST;

Storing complex data types

A BST can be instantiated with a Comparator to allow storing and organizing the elements in a custom order.

For example, to store "Person" objects and create the tree based on the Person.age:

var compareFunction = function (a, b) {
  if (a.age == b.age) return 0;
  return a.age < b.age ? -1 : 1;
};
var bst = new BST(compareFunction);

bst.insert(n)

var bst = new BST();
bst.insert(4);
bst.insert(8);
bst.insert(10);
bst.insert(2);
bst.insert(1);
bst.insert(3);
bst.insert(0);
bst.insert(5);
bst.insert(100);

/**
 * Then, you're gonna have something like:
 * 
 *            4
 *       2          8
 *    1     3    5     10
 *  0    2.5               100
 */

bst.root

Points to the Node that is the root of the tree, for the tree above, bst.root will be:

{ 
  value: 4,
  parent: null,
  left: { value: 2, ...},
  right: { value: 8, ...}
}

bst.contains(n)

Returns if the tree contains the passed element (in O(lg n))

bst.contains(4); //true
bst.contains(3); //true
bst.contains(0); //true
bst.contains(22); //false
bst.contains(-1); //false

bst.remove(n)

Removes an element from the tree and reorganizes it (in (O(lg n))

/**
 *            4
 *       2          8
 *    1     3    5     10
 *  0    2.5               100
 */

bst.remove(0);

/**
 *            4
 *       2          8
 *    1     3    5     10
 *       2.5               100
 */

bst.remove(4);

/**
 *            5
 *       2          8
 *    1     3          10
 *       2.5               100
 */

bst.remove(2)
/**
 *            5
 *      2.5          8
 *    1     3          10
 *                       100
 */

bst.size

Returns the size of the tree