Skip to content

Instantly share code, notes, and snippets.

@khaled0fares
Last active October 2, 2016 13:32
Show Gist options
  • Save khaled0fares/3457703c5caf4bfef92126fd846bab25 to your computer and use it in GitHub Desktop.
Save khaled0fares/3457703c5caf4bfef92126fd846bab25 to your computer and use it in GitHub Desktop.
Binary Search Tree in js
class NodeTree{
constructor(data, leftNode, rightNode){
this.data = data;
this.leftNode = leftNode;
this.rightNode = rightNode;
}
display(){
return this.data
}
}
class BST{
constructor(){
this.root = null;
}
insert(data){
let newNode = new NodeTree(data, null, null), current = this.root, parent;
if(this.root == null){
this.root = newNode;
return;
}
while(current != null){
parent = current;
if(data < current.data){
current = current.leftNode;
if(current == null){
parent.leftNode = newNode;
return;
}
}
else{
current = current.rightNode
if(current == null){
parent.rightNode= newNode;
return;
}
}
}
}
find(data){
let current = this.root;
while(data != current.data){
if(data < current.data) { current = current.leftNode; }
else{ current = current.rightNode; }
if(current == null){return}
}
return current
}
findParent(data){
let current = this.root, parent;
while(data != current.data){
parent = current;
if(data < current.data) { current = current.leftNode; }
else{ current = current.rightNode; }
if(current == null){return}
}
return parent
}
getMin(node){
let current = node || this.root,parent = current;
while(current != null){
parent = current;
current = current.leftNode
}
return parent.data;
}
getMax(node){
let current = node || this.root,parent = current;
while(current != null){
parent = current;
current = current.rightNode
}
return parent.data;
}
inOrder(node){
if(node != null){
this.inOrder(node.leftNode);
node.display();
this.inOrder(node.rightNode);
}
}
preOrder(node){
if(node != null){
node.display();
this.preOrder(node.leftNode);
this.preOrder(node.rightNode);
}
}
postOrder(node){
if(node != null){
this.postOrder(node.leftNode);
this.postOrder(node.rightNode);
node.display();
}
}
delete(data){
let ele = this.find(data), parent = this.findParent(data);
//Node is a leaf
if(ele.leftNode == null && ele.rightNode == null){
if(ele == this.root) this.root = null; return
if(parent.leftNode == ele) parent.leftNode = null
else parent.rightNode = null
}
/*Node has one child*/
else if(ele.leftNode == null) parent.rightNode = ele.rightNode;
else if(ele.rightNode == null) parent.leftNode = ele.leftNode;
/*Node has two children*/
else{
let smallest = this.getMin(ele);
ele.data = smallest;
delete(smallest);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment