class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
search(value) {
return this.searchVal(this.root, value);
}
searchVal(root, value) {
if (root === null) {
return false;
} else if (root.value == value) {
return root;
} else if (value < root.value) {
return this.searchVal(root.left, value);
} else if (value > root.value) {
return this.searchVal(root.right, value);
}
}
insert(value) {
if (this.root === null) {
this.root = new Node(value);
return this;
}
this.root = this.insertVal(this.root, value);
}
insertVal(node, value) {
if (node === null) {
return new Node(value);
} else if (value < node.value) {
node.left = this.insertVal(node.left, value);
} else {
node.right = this.insertVal(node.right, value);
}
return node;
}
remove(value) {
this.root = this.removeVal(this.root, value);
}
removeVal(root, value) {
// console.log(root.value);
if (root === null) {
return null;
}
// if value is less than the node value,
// delete the node in the left subtree
if(value < root.value) {
root.left = this.removeVal(root.left, value);
} else if (value > root.value) {
root.right = this.removeVal(root.right, value);
} else { // found the node to delete
// only right subtree or leaf node
if (root.left === null) {
return root.right;
} else if (root.right === null) {
return node.left;
} else { // Case 3: The node to be deleted has 2 child nodes
// Find the minimum value in the right subtree
// ie the inorder successor of the value to be deleted
root.value = this.findMin(root.right).value;
// Delete the inorder successor
root.right = this.removeVal(root.right, root.value);
}
}
return root;
}
printInOrder() {
this.Inorder(this.root);
console.log();
}
// inorder traversal of the BST
Inorder(root) {
if (root === null) { return; }
this.Inorder(root.left);
// console.log(root.value + ", ");
process.stdout.write(root.value + ", ");
this.Inorder(root.right);
}
findMin(root) {
while (root.left !== null) {
root = root.left;
}
// console.log("Min value is: " + root.value);
return root;
}
}
function traverse(node) {
const tree = { value: node.value };
tree.left = node.left === null ? null : traverse(node.left);
tree.right = node.right === null ? null : traverse(node.right);
return tree;
}
const bst = new BinarySearchTree();
bst.insert(9);
bst.insert(4);
bst.insert(20);
bst.insert(1);
bst.insert(15);
bst.insert(170);
bst.insert(6);
console.log(bst);
// Inorder(bst.root);
bst.printInOrder();
bst.remove(20);
bst.printInOrder();
// console.log(bst.search(15));
// console.log(JSON.stringify(traverse(bst.root)));
