Skip to content

Instantly share code, notes, and snippets.

@aaronjwood
Created November 15, 2015 18:21
Show Gist options
  • Save aaronjwood/96ef576fdb55590a3f48 to your computer and use it in GitHub Desktop.
Save aaronjwood/96ef576fdb55590a3f48 to your computer and use it in GitHub Desktop.
Binary search tree implementation in JavaScript
var Node = function (value, left, right) {
this.value = value;
this.left = left;
this.right = right;
};
function insert(root, v) {
if (root == null) {
root = new Node(v, null, null);
}
else if (v < root.value) {
root.left = insert(root.left, v);
}
else {
root.right = insert(root.right, v);
}
return root;
}
function traverse(root) {
if (root == null) {
return;
}
traverse(root.left);
traverse(root.right);
}
var root = null;
const SIZE = 2000000;
var a = [];
console.log("Generating random array with " + SIZE + " values...");
console.time("generate");
for (var i = 0; i < SIZE; i++) {
a[i] = Math.floor(Math.random() * 10000);
}
console.timeEnd("generate");
console.log();
console.log("Filling the tree with " + SIZE + " nodes...");
console.time("fill");
for (var i = 0; i < SIZE; i++) {
root = insert(root, a[i]);
}
console.timeEnd("fill");
console.log();
console.log("Traversing all " + SIZE + " nodes in tree...");
console.time("traverse");
traverse(root);
console.timeEnd("traverse");
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment