Skip to content

Instantly share code, notes, and snippets.

@connor11528
Last active July 13, 2020 05:31
Show Gist options
  • Star 2 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save connor11528/b882e75b6f457406feae73858b0a3199 to your computer and use it in GitHub Desktop.
Save connor11528/b882e75b6f457406feae73858b0a3199 to your computer and use it in GitHub Desktop.
Binary search tree implemented in Javascript
class BinarySearchTree {
constructor(){
this.root = null;
}
// add a node to the tree
add(value){
let newNode = { value, left: null, right: null};
// set the root if we don't have one
if(this.root == null){
this.root = newNode;
return;
}
let current = this.root;
while(true){
// check for right
if(value > current.value){
// add right
if(!current.right){ current.right = newNode; break; }
current = current.right;
// check for left
} else if(value < current.value){
// add left
if(!current.left){ current.left = newNode; break; }
current = current.left;
} else {
// if it's the same ignore
break;
}
}
}
// search for a specific value
contains(value){
let current = this.root;
while(current){
if(current.value == value){
return true;
} else if (current.value > value){
current = current.left;
} else {
current = current.right;
}
}
return false;
}
}
class DepthFirstTraverser extends BinarySearchTree {
// pre-order -> root, left, right
// in-order -> left, root, right
// post-order -> left, right, root
consstructor(){
this.traverseMethod = 'pre-order';
}
setTraverseMethod(traverseMethod){
if(traverseMethod == 'pre-order' || traverseMethod == 'in-order' || traverseMethod == 'post-order'){
this.traverseMethod = traverseMethod;
} else {
console.error('Not a valid search method, must be "pre-order", "in-order" or "post-order"');
}
}
getTraverseMethod(){
return this.traverseMethod;
}
traverse(){
switch(this.traverseMethod){
case 'pre-order':
this.preOrderTraverse(value);
break;
case 'in-order':
this.inOrderTraverse(value);
break;
case 'post-order':
this.postOrderTraverse(value);
break;
default:
console.error('invalid traverse method');
}
}
preOrderTraverse(value){
}
inOrderTraverse(value){
}
postOrderTraverse(value){
}
}
class BreadthFirstTraverser extends BinarySearchTree {
traverse(value){
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment