Skip to content

Instantly share code, notes, and snippets.

@jasterix
Created August 16, 2020 17:15
Show Gist options
  • Save jasterix/c47d5c96732e7d6f5bea5cdf1904226f to your computer and use it in GitHub Desktop.
Save jasterix/c47d5c96732e7d6f5bea5cdf1904226f to your computer and use it in GitHub Desktop.
Creating and working with a binary search tree
class Node {
constructor(value){
this.value = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor(){
this.root = null;
}
insert(value){
var newNode = new Node(value);
if(this.root === null){
this.root = newNode;
return this;
}
var current = this.root;
while(true){
if(value === current.value) return undefined;
if(value < current.value){
if(current.left === null){
current.left = newNode;
return this;
}
current = current.left;
} else {
if(current.right === null){
current.right = newNode;
return this;
}
current = current.right;
}
}
}
find(value){
if(this.root === null) return false;
var current = this.root,
found = false;
while(current && !found){
if(value < current.value){
current = current.left;
} else if(value > current.value){
current = current.right;
} else {
found = true;
}
}
if(!found) return undefined;
return current;
}
contains(value){
if(this.root === null) return false;
var current = this.root,
found = false;
while(current && !found){
if(value < current.value){
current = current.left;
} else if(value > current.value){
current = current.right;
} else {
return true;
}
}
return false;
}
}
// 10
// 5 13
// 2 7 11 16
var tree = new BinarySearchTree();
tree.insert(10)
tree.insert(5)
tree.insert(13)
tree.insert(11)
tree.insert(2)
tree.insert(16)
tree.insert(7)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment