Skip to content

Instantly share code, notes, and snippets.

@liamgriffiths
Last active January 1, 2016 22:59
Show Gist options
  • Save liamgriffiths/8213595 to your computer and use it in GitHub Desktop.
Save liamgriffiths/8213595 to your computer and use it in GitHub Desktop.
/**
* Binary Search Tree
*
* This is a tree data structure that orders the nodes of the tree such that:
* - The left subtree only contains nodes of lesser values
* - The right subtree only contains nodes of greater values
* - There are no duplicate nodes
*
* What this is good for:
* - Storing unique values
* - Fast searching, insertion
* - Implementing Sets, Multisets, Maps
*
* References:
* https://en.wikipedia.org/wiki/Binary_search_tree
* https://en.wikipedia.org/wiki/In-order_traversal
*/
function BinarySearchTree() {
this.root = undefined;
}
/**
* Search the tree for a value
* @param {Number} value
* @param {Node} start - optionally start search from another node
* @returns {Node} - node from tree if it is found, otherwise undefined
*/
BinarySearchTree.prototype.search = function(value, start) {
var node = start || this.root;
while (node) {
if (value < node.value) {
node = node.left;
} else if (value > node.value) {
node = node.right;
} else if (node.value === value) {
break;
}
}
return node;
};
/**
* Iterate through all the nodes of a subtree beginning at specified node
* @param {Function} fn - callback function to be applied to each node
* @param {String} order - optionally traverse the tree in alternative orders
*/
BinarySearchTree.prototype.traverse = function(node, fn, order) {
var traversals = {
// depth-first in-order traversal (min value node -> max value node)
inOrder: function(node, visit) {
if (! node) return;
traversals.inOrder(node.left, visit);
visit(node);
traversals.inOrder(node.right, visit);
},
// depth-first pre-order traversal (root node -> min node -> max node)
preOrder: function(node, visit) {
if (! node) return;
visit(node);
traversals.preOrder(node.left, visit);
traversals.preOrder(node.right, visit);
},
// depth-first post-order traversal (deepest min node -> root node)
postOrder: function(node, visit) {
if (! node) return;
traversals.postOrder(node.left, visit);
traversals.postOrder(node.right, visit);
visit(node);
}
};
var traverseOrder = order || 'inOrder';
return traversals[traverseOrder](node, fn);
};
/**
* Iterate through all the nodes of the tree and apply a function.
* @param {Function} fn - callback function to be applied to each node
* @param {String} order - optionally traverse the tree in alternative orders
* @returns {BinarySearchTree} - this
*/
BinarySearchTree.prototype.each = function(fn, order) {
this.traverse(this.root, fn, order);
return this;
};
/**
* Traverse the tree and count the nodes.
* @returns {Number} - count of the nodes in the tree
*/
BinarySearchTree.prototype.size = function() {
var count = 0;
this.each(function(node) { count++; });
return count;
};
/**
* Inserts a new node into the tree if it does not already exist
* @param {Number} value - new value to be inserted into tree
* @returns {BinarySearchTree} - this
*/
BinarySearchTree.prototype.insert = function(value) {
if (! this.root) {
this.root = new Node(value); // Set root node if it is not defined
} else {
var node = this.root;
while (node) {
if (value < node.value) {
if (! node.left) node.left = new Node(value);
node = node.left;
} else if (value > node.value) {
if (! node.right) node.right = new Node(value);
node = node.right;
} else {
break;
}
}
}
return this;
};
/**
* Remove a value from the tree
* @returns {BinarySearchTree} - this
*/
BinarySearchTree.prototype.remove = function(value) {
// TODO: this is basically a duplicated search, refactor this
var node = this.root;
var parent;
while (node) {
if (value < node.value) {
parent = node;
node = node.left;
} else if (value > node.value) {
parent = node;
node = node.right;
} else if (node.value === value) {
break;
}
}
if (node) {
if (node.left && node.right) {
// Deleting a node with two children
if (node.left < node.right ) {
node.value = node.left.value;
return this.remove(node.value);
} else {
node.value = node.right.value;
return this.remove(node.value);
}
} else if (node.left || node.right) {
// Deleting node with one child, replace node with child
var child = node.left || node.right;
if (parent.left == node) {
parent.left = child;
} else {
parent.right = child;
}
} else {
// Delete leaf node with no children, remove references to node
if (parent.left == node) {
parent.left = undefined;
} else {
parent.right = undefined;
}
}
}
return this;
};
/**
* Traverse the tree 'in-order' and return all the nodes in order visited
* @returns {Array} - array of Node objects
*/
BinarySearchTree.prototype.sort = function(node) {
var sorted = [];
this.traverse(this.root, function(node) { sorted.push(node); });
return sorted;
};
/**
* Finds the smallest value node in the tree - the left-most node.
* @returns {Node}
*/
BinarySearchTree.prototype.min = function() {
var min = this.root;
while (min.left) min = min.left;
return min;
};
/**
* Finds the greatest value node in the tree - the right-most node.
* @returns {Node}
*/
BinarySearchTree.prototype.max = function() {
var max = this.root;
while (max.right) max = max.right;
return max;
};
function Node(value) {
this.value = value;
this.left = undefined;
this.right = undefined;
}
module.exports = BinarySearchTree;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment