Binary Search Tree

binary_search_tree.js

/**
 * Data Type
 */
// Tree a = EmptyTree | Node a (Tree a) (Tree a)


/**
 * Value Constructors
 */

var EmptyTree = {};

function Node(v, left, right) {
  return {
    node: v,
    left: left,
    right: right
  };
}


/**
 * Tree Functions
 */

// a -> Tree a
function singleton(v) {
  return Node(v, EmptyTree, EmptyTree);
}


// a -> Tree a -> Tree a
function treeInsert(v, tree) {
  var node = tree.node,
      left = tree.left,
      right = tree.right;

  if(tree === EmptyTree) {
    return singleton(v);
  }

  if(v === node) {
    return Node(v, left, right);
  } else if(v < node) {
    return Node(node, treeInsert(v, left), right);
  } else {
    return Node(node, left, treeInsert(v, right));
  }
}

// a -> Tree a -> Boolean
function isInTree(v, tree) {
  var node = tree.node,
      left = tree.left,
      right = tree.right;

  if(tree === EmptyTree) {
    return false;
  }

  if(v === node) {
    return true;
  } else if(v < node) {
    return isInTree(v, left);
  } else {
    return isInTree(v, right);
  }

}

var list = [5, 3, 7, 1, 4, 6, 8];

var tree = list.reduce(function(acc, v) {
  return treeInsert(v, acc);
}, EmptyTree);
// => { node: 5,
//      left:
//       { node: 3,
//         left: { node: 1, left: {}, right: {} },
//         right: { node: 4, left: {}, right: {} } },
//      right:
//       { node: 7,
//         left: { node: 6, left: {}, right: {} },
//         right: { node: 8, left: {}, right: {} } } }

isInTree(1, tree);
// => true

isInTree(9, tree);
// => false