BinarySearchTree
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162
class Node {
constructor(value) {
this.left = null;
this.right = null;
this.value = value;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
insert(value, parent) {
const node = new Node(value);
if (!this.root) {
this.root = node;
return;
} else {
if (!parent) {
parent = this.root;
}
let nextNode = null;
if (value > parent.value) {
nextNode = parent.right;
if (nextNode) {
this.insert(value, nextNode);
} else {
parent.right = node;
return;
}
} else {
nextNode = parent.left;
if (nextNode) {
this.insert(value, nextNode);
} else {
parent.left = node;
return;
}
}
}
}
lookup(value, parent) {
if (!parent) {
parent = this.root;
}
if (parent.value === value) {
return true;
}
let nextNode = null;
if (value > parent.value) {
nextNode = parent.right;
if (nextNode) {
return this.lookup(value, nextNode);
} else {
return false;
}
} else {
nextNode = parent.left;
if (nextNode) {
return this.lookup(value, nextNode);
} else {
return false;
}
}
}
remove(value) {
// TODO: I test few test and it worked but i am not sure it'll work for other inputs
let currentNode = this.root;
let nextNode = null;
let nextLeftNode = null;
while (currentNode) {
if (value > currentNode.value) {
nextNode = currentNode.right;
if (nextNode && nextNode.value === value) {
if (!nextNode.right) {
currentNode.right = null;
} else {
let leafNode = nextNode.right;
let parentOfLeaf = nextNode;
let pointerNode = nextNode.right;
while (pointerNode) {
parentOfLeaf = leafNode;
leafNode = pointerNode;
pointerNode = leafNode.left;
}
console.log("#####", leafNode, parentOfLeaf);
if (!leafNode) {
nextLeftNode = nextNode.left;
leafNode = nextNode.right;
}
let leafNodeRight = leafNode.right;
currentNode.right = leafNode;
parentOfLeaf.left = leafNodeRight;
currentNode.right.right = nextNode.right;
currentNode.right.left = nextNode.left;
if (nextLeftNode) {
currentNode.right.left = nextLeftNode;
}
}
return;
} else {
currentNode = currentNode.right;
}
} else if (value < currentNode.value) {
nextNode = currentNode.left;
if (nextNode && nextNode.value === value) {
if (!nextNode.right) {
currentNode.left = null;
} else {
let leafNode = nextNode.right.left;
let parentOfLeaf = nextNode;
let pointerNode = nextNode.right;
while (leafNode) {
leafNode = pointerNode;
pointerNode = leafNode.left;
}
if (!leafNode) {
nextLeftNode = nextNode.left;
leafNode = nextNode.right;
}
let leafNodeRight = leafNode.right;
currentNode.left = leafNode;
parentOfLeaf.right = leafNodeRight;
// currentNode.left.right = ;
// currentNode.left.left = nextNode.left;
if (nextLeftNode) {
currentNode.left.left = nextLeftNode;
}
}
return;
} else {
currentNode = currentNode.left;
}
} else if (value === currentNode.value) {
console.log(currentNode);
return true;
}
}
return false;
}
}
const binarySearchTree = new BinarySearchTree();
console.log(binarySearchTree);
[41, 20, 74, 11, 29, 50, 91, 32, 80, 99, 75, 81, 92, 76].forEach((item) => {
binarySearchTree.insert(item);
});
console.log(binarySearchTree.lookup(21));
console.log(binarySearchTree.lookup(23));
console.log(binarySearchTree.lookup(9));
console.log(binarySearchTree.remove(74));
console.log(binarySearchTree.remove(75));
console.log(binarySearchTree.remove(20));
console.log(JSON.stringify(binarySearchTree, null, 2));
JavaScript
INFO