Created
September 21, 2016 15:11
-
-
Save mitrakmt/4b51508c220cad3ef97b65b95072a2eb to your computer and use it in GitHub Desktop.
Implement a Binary Search Tree in JavaScript
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// This Binary Search Tree is implemented using the prototypal pattern | |
var BinarySearchTree = function(value) { | |
var instance = Object.create(BinarySearchTree.prototype); | |
instance.value = value; | |
// a BST where all values are higher than than the current value. | |
instance.right = undefined; | |
// a binary search tree (BST) where all values are lower than than the current value. | |
instance.left = undefined; | |
return instance | |
}; | |
BinarySearchTree.prototype.insert = function (value) { | |
// accepts a value and places in the tree in the correct position. | |
var node = BinarySearchTree(value); | |
function recurse(bst) { | |
if (bst.value > value && bst.left === undefined) { | |
bst.left = node; | |
} else if (bst.value > value) { | |
recurse(bst.left); | |
} else if (bst.value < value && bst.right === undefined) { | |
bst.right = node; | |
} else if (bst.value < value) { | |
recurse(bst.right); | |
} | |
} | |
recurse(this); | |
} | |
BinarySearchTree.prototype.contains = function (value) { | |
var doesContain = false; | |
//accepts a value and returns a boolean reflecting whether or not the value is contained in the tree. | |
function recurse(bst) { | |
if (bst.value === value) { | |
doesContain = true;; | |
} else if (bst.left !== undefined && value < bst.value) { | |
recurse(bst.left); | |
} else if (bst.right !== undefined && value > bst.value) { | |
recurse(bst.right) | |
} | |
} | |
recurse(this); | |
return doesContain; | |
} | |
BinarySearchTree.prototype.depthFirstLog = function (callback) { | |
//accepts a callback and executes it on every value contained in the tree. | |
function recurse(bst) { | |
callback.call(bst, bst.value) | |
if (bst.left !== undefined) { | |
recurse(bst.left) | |
} | |
if (bst.right !== undefined) { | |
recurse(bst.right); | |
} | |
} | |
recurse(this); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Hi, thank you for this interesting solution.
How can one instrument this solution to run this in a chrome browser?
For learning & demonstration purposes, may I ask you for a run utility with this sample