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));
class Node {
constructor(value) {
this.left = null;
this.right = null;
this.value = value;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
insert(value) {
const newNode = new Node(value);
if (!this.root) {
this.root = newNode;
} else {
let currentNode = this.root;
while (true) {
if (value < currentNode.value) {
// Left
if (!currentNode.left) {
currentNode.left = newNode;
return this;
}
currentNode = currentNode.left;
} else {
// Right
if (!currentNode.right) {
currentNode.right = newNode;
return this;
}
currentNode = currentNode.right;
}
}
}
}
lookup(value) {
if (!this.root) {
return false;
}
let currentNode = this.root;
while (currentNode) {
if (value < currentNode.value) {
currentNode = currentNode.left;
} else if (value > currentNode.value) {
currentNode = currentNode.right;
} else if (currentNode.value === value) {
return true;
}
}
return false;
}
remove(value) {
if (!this.root) {
return false;
}
let currentNode = this.root;
let parentNode = null;
while (currentNode) {
if (value < currentNode.value) {
parentNode = currentNode;
currentNode = currentNode.left;
} else if (value > currentNode.value) {
parentNode = currentNode;
currentNode = currentNode.right;
} else if (currentNode.value === value) {
//We have a match, get to work!
//Option 1: No right child:
if (currentNode.right === null) {
if (parentNode === null) {
this.root = currentNode.left;
} else {
//if parent > current value, make current left child a child of parent
if (currentNode.value < parentNode.value) {
parentNode.left = currentNode.left;
//if parent < current value, make left child a right child of parent
} else if (currentNode.value > parentNode.value) {
parentNode.right = currentNode.left;
}
}
//Option 2: Right child which doesnt have a left child
} else if (currentNode.right.left === null) {
currentNode.right.left = currentNode.left;
if (parentNode === null) {
this.root = currentNode.right;
} else {
//if parent > current, make right child of the left the parent
if (currentNode.value < parentNode.value) {
parentNode.left = currentNode.right;
//if parent < current, make right child a right child of the parent
} else if (currentNode.value > parentNode.value) {
parentNode.right = currentNode.right;
}
}
//Option 3: Right child that has a left child
} else {
//find the Right child's left most child
let leftmost = currentNode.right.left;
let leftmostParent = currentNode.right;
while (leftmost.left !== null) {
leftmostParent = leftmost;
leftmost = leftmost.left;
}
//Parent's left subtree is now leftmost's right subtree
leftmostParent.left = leftmost.right;
leftmost.left = currentNode.left;
leftmost.right = currentNode.right;
if (parentNode === null) {
this.root = leftmost;
} else {
if (currentNode.value < parentNode.value) {
parentNode.left = leftmost;
} else if (currentNode.value > parentNode.value) {
parentNode.right = leftmost;
}
}
}
return true;
}
}
}
}
const binarySearchTree = new BinarySearchTree();
console.log(binarySearchTree);
binarySearchTree.insert(9);
binarySearchTree.insert(20);
binarySearchTree.insert(4);
binarySearchTree.insert(1);
binarySearchTree.insert(6);
binarySearchTree.insert(15);
binarySearchTree.insert(170);
console.log(binarySearchTree.lookup(21));
console.log(binarySearchTree.lookup(23));
console.log(binarySearchTree.lookup(9));
binarySearchTree.remove(170);
console.log(JSON.stringify(binarySearchTree, null, 2));
