Skip to content

Instantly share code, notes, and snippets.

@yawboakye
Last active December 17, 2015 23:59
Show Gist options
  • Save yawboakye/5693166 to your computer and use it in GitHub Desktop.
Save yawboakye/5693166 to your computer and use it in GitHub Desktop.
Tiny binary search tree implementation in JavaScript (does not balance automatically)
// javascript implementation of a binary search tree
var BST = function ( val ) {
this.val = val;
this.lc = this.rc = null;
}
BST.prototype = {
constructor: BST,
insert: function( val ) {
this.val == null
? this.val = val
: this.val == val
? null
: this.val > val
? ( !! this.lc ? this.lc.insert( val ) : this.lc = new BST( val ) )
: ( !! this.rc ? this.rc.insert( val ) : this.rc = new BST( val ) )
},
contains: function( val ) {
return !this.val
? false
: this.val == val
? true
: this.val > val
? ( !! this.lc ? this.lc.contains( val ) : false )
: ( !! this.rc ? this.rc.contains( val ) : false )
},
traverse: function ( fn ) {
if ( !this.val ) return;
if ( this.lc ) this.lc.traverse( fn );
fn.call( this );
if ( this.rc ) this.rc.traverse( fn );
},
size: function() {
if ( !this.val ) return 0
var acc = 1; // keep count because we are going down to different lanes
return (
function () {
if ( !this.lc && !this.rc ) return acc;
else {
if ( this.lc ) acc += this.lc.size();
if ( this.rc ) acc += this.rc.size();
}
return acc;
}).call( this );
},
}
function test () {
var fill = ( function fill ( size ) {
var r = [];
while ( r.length < size ) {
var n = Math.floor( Math.random() * size + 1 );
if (r.indexOf( n ) == -1)
r.push( n );
}
return r;
});
var run = function ( size ) {
var bst = new BST()
, inp = fill( size )
, start
, timeTaken;
start = +new Date
for ( var i = 0; i < inp.length; ++i )
bst.insert( inp[ i ] );
timeTaken = +new Date - start;
console.log("\nTESTING with input size: %d", size);
console.log("---------------------------------------------------------------")
console.log( bst );
console.log("%s: %d\n%s: %d ms\n"
,'Binary Search Tree of size', bst.size()
, 'Time taken', timeTaken);
// Uncomment this code to log every node in this tree
// bst.traverse( function () {
// console.log( this.val );
// } ); // tree traversal
console.log("---------------------------------------------------------------\n\n")
}
// run(1);
run(10);
run(100);
run(1000);
run(10000);
}
test();
@yawboakye
Copy link
Author

Added test with various input sizes

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment