Skip to content

Instantly share code, notes, and snippets.

@eakray

eakray/BST.js

Last active January 30, 2016 00:21
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save eakray/94e1a38351f38f7338c3 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save eakray/94e1a38351f38f7338c3 to your computer and use it in GitHub Desktop.
Download ZIP
Binary Search Tree
Raw
BST.js
function Node(value){
this.value = value;
this.left = null;
this.right = null;
this.parent = null;
}
function BST(){
this.root = null;
}
BST.prototype.insert = function(value){
var node = new Node(value);
if(this.root === null){
this.root = node;
}
else{
var position = this.root;
while(position){
if(value > position.value){
if(position.right === null){
position.right = node;
node.parent = position;
break;
}
position = position.right;
}
if(value < position.value){
if(position.left === null){
position.left = node;
node.parent = position;
break;
}
position = position.left;
}
if(value === position.value){
break;
}
}
}
var depthTuple = this.depthCheck();
var minDepth = depthTuple[0];
var maxDepth = depthTuple[1];
if(maxDepth / 3 > minDepth){
this.rebalance();
}
};
BST.prototype.max = function(){
var position = this.root;
while (position.right !== null){
position = position.right;
}
return position.value;
};
BST.prototype.min = function(){
var position = this.root;
while (position.left !== null){
position = position.left;
}
return position.value;
};
//Depth-first Traversals
BST.prototype.preOrder = function(callback){
(function recurse(node){
if (node === null){
return;
}
callback(node.value);
recurse(node.left);
recurse(node.right);
})(this.root);
};
BST.prototype.inOrder = function(callback){
(function recurse(node){
if (node === null){
return;
}
recurse(node.left);
callback(node.value);
recurse(node.right);
})(this.root);
};
BST.prototype.postOrder = function(callback){
(function recurse(node){
if(node === null){
return;
}
recurse(node.left);
recurse(node.right);
callback(node.value);
})(this.root);
};
BST.prototype.toArray = function(){
var results = [];
(function recurse(node){
if (node === null){
return;
}
recurse(node.left);
results.push(node.value);
recurse(node.right);
})(this.root);
return results;
};
//Breadth-first Traversals
BST.prototype.breadthFirst = function(callback){
var children = [this.root];
while(children.length !== 0){
var newChildren = [];
for(var i = 0; i <= children.length-1; i++){
callback(children[i].value);
if (children[i].left){
newChildren.push(children[i].left);
}
if (children[i].right){
newChildren.push(children[i].right);
}
}
children = newChildren;
}
};
BST.prototype.clear = function(){
this.root = null;
};
BST.prototype.size = function(){
var size = 0;
this.inOrder(function(node) {
size++;
});
return size;
};
BST.prototype.isLeaf = function(node){
return ((node.left === null) && (node.right === null));
};
BST.prototype.rebalance = function(){
var values = [];
this.inOrder(function(data){
values.push(data);
});
this.clear();
var midIndex = Math.floor(values.length/2);
var median = values[midIndex];
this.root = new Node(median);
var left = values.slice(0, midIndex);
var right = values.slice(midIndex+1);
this.fillTree(left, this.root);
this.fillTree(right, this.root);
};
BST.prototype.fillTree = function(values, node){
if(values.length === 0){
return false;
}
var midIndex = Math.floor(values.length/2);
var median = values[midIndex];
this.insert(median);
var left = values.slice(0, midIndex);
var right = values.slice(midIndex+1);
this.fillTree(left, node);
this.fillTree(right, node);
};
BST.prototype.depthCheck = function(){
var children = [this.root];
var maxLevels = 0;
var minLevels = 0;
var separated = false;
while(children.length !== 0){
var newChildren = [];
maxLevels++;
for(var i = 0; i < children.length; i++){
if(children[i].left){
newChildren.push(children[i].left);
}
if(children[i].right){
newChildren.push(children[i].right);
}
if(!separated && (!children[i].left || !children[i].right)){
separated = true;
minLevels = maxLevels;
}
}
children = newChildren;
}
return [minLevels, maxLevels];
};
BST.prototype.contains = function(value){
var position = this.root;
while(position.value !== value){
if(value>position.value){
if(position.right === null){
return false;
}
position = position.right;
}
if(value < position.value){
if(position.left === null){
return false;
}
position = position.left;
}
}
return position;
};
BST.prototype.remove = function(value){
var position = this.contains(value);
var removed = position;
var results = [];
if(position === false){
return 'tree does not contain such a value';
}
if (this.isLeaf(position)){
position = position.parent;
if(position.right !== null){
if(position.right.value === value){
position.right = null;
}
}
if(position.left !== null){
if(position.left.value === value){
position.left = null;
}
}
return removed;
}
if(!this.isLeaf(position) && position.parent !== null){
(function recurse(node){
if (node === null){
return;
}
recurse(node.left);
if(node.value !== position.value){
results.push(node.value);
}
recurse(node.right);
})(position);
position = position.parent;
if(position.left.value === value){
position.left = null;
}
if(position.right.value === value){
position.right = null;
}
this.fillTree(results, position);
return value;
}
if(position.parent === null){
(function recurse(node){
if (node === null){
return;
}
recurse(node.left);
if(node.value !== position.value){
results.push(node.value);
}
recurse(node.right);
})(position);
this.root = null;
var midIndex = Math.floor(results.length/2);
var median = results[midIndex];
this.insert(median);
var node = this.root;
this.fillTree(results, node);
return value;
}
};
BST.prototype.kthSmallest = function(value){
var order = this.toArray();
return order[value-1];
};
BST.prototype.kthLargest = function(value){
var order = this.toArray();
var largest = (order.length-1)-(value-1);
if(largest >= 0 && !(largest > order.length-1)){
return order[largest];
}
return 'out of bounds';
};
BST.prototype.lowestCommonAncestor = function(first, second){
var args = [];
var result = [];
args.push(arguments[0]);
args.push(arguments[1]);
args.sort(function(a,b){
return a - b;
});
if(args[0] === args[1]){
return 'values must not be identical';
}
if(!this.contains(first) || !this.contains(second)){
return 'both values must be present in the tree';
}
(function recurse(node){
if (node === null){
return;
}
if((node.value > args[0]) && (node.value < args[1])
|| node.value === args[0]
|| node.value === args[1]){
result.push(node.value);
}
recurse(node.left);
recurse(node.right);
})(this.root);
return result[0];
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment