JavaScript binary search tree + tests

bst.js

/**
 * Copyright 2017, Joshua Gross, All Rights Reserved.
 * Released under the MIT license.
 */

/**
 * Each BST is represented as its own root.
 * BSTs have no rebalancing, so tree shape can get gnarly real quick!
 */
function BST (key, value, left, right) {
  this.key = key;
  this.value = value;
  this.left = left || null;
  this.right = right || null;
  return this;
}

BST.prototype.insert = function (key, value) {
  if (key > this.key && this.right) {
    this.right.insert(key, value);
  } else if (key > this.key && !this.right) {
    this.right = new BST(key, value, null, null);
  } else if (key < this.key && this.left) {
    this.left.insert(key, value);
  } else if (key < this.key && !this.left) {
    this.left = new BST(key, value, null, null);
  } else {
    // key is equal? update in-place?
    this.value = value;
  }
};

BST.prototype.max = function () {
  if (this.right) {
    return this.right.max();
  }
  
  return this.value;
};

BST.prototype.min = function () {
  if (this.left) {
    return this.left.min();
  }
  
  return this.value;
};

BST.prototype.height = function () {
  var l = (this.left ? this.left.height() : 0) + 1;
  var r = (this.right ? this.right.height() : 0) + 1;
  return Math.max(l, r);
};

var x = new BST(0, 0);
x.insert(1,1);
x.insert(10,10);
x.insert(2,2);
x.insert(11,11);
x.insert(3,3);
x.insert(15,15);
x.insert(4,4);
x.insert(0,0);
x.insert(13,13);

console.log(x.min(), x.max(), x.height());

// Insert a bunch of random data
var y = genLargeTree(100000);
console.log(y.min(), y.max(), y.height());

// Do this a bunch of times. Get the average, min, max of heights.
var root = genLargeTree(100000);
var rh = root.height();
var y = new BST(rh, rh);
var sum = 0;
for (var i = 0; i < 1000; i++) {
  console.log('Generating random tree', i);
  var z = genLargeTree(100000);
  var h = z.height();
  sum += h;
  y.insert(h, h);
}
var avg = sum / 1000;

console.log('many trees heights:', y.min(), y.max(), avg);

function genLargeTree (n) {
  var z = Math.floor(Math.random()*n*n);
  var y = new BST(z, z);
  for (var i = 0; i < n; i++) {
    z = Math.floor(Math.random()*n);
    y.insert(z, z)
  }

  return y;
}