BST
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152
class BSTNode {
public left: BSTNode | null;
public right: BSTNode | null;
public value: number;
constructor(value: number) {
this.left = null;
this.right = null;
this.value = value;
}
}
class BinarySearchTree {
public root: BSTNode | null;
constructor() {
this.root = null;
}
insert(value: number) {
if (this.root === null) {
this.root = new BSTNode(value);
} else {
const newNode = new BSTNode(value);
let currentNode = this.root;
while (currentNode !== null) {
if (value < currentNode.value) {
if (currentNode.left === null) {
currentNode.left = newNode;
break;
}
currentNode = currentNode.left;
} else {
if (currentNode.right === null) {
currentNode.right = newNode;
break;
}
currentNode = currentNode.right;
}
}
}
}
lookup(value: number) {
if (this.root === null) {
return false;
}
let currentNode: BSTNode | null = this.root;
while (currentNode !== null) {
if (value === currentNode.value) {
return true; // Value found
}
if (value < currentNode.value) {
currentNode = currentNode.left;
} else {
currentNode = currentNode.right;
}
}
return false; // Value not found
}
remove(value: number) {
if (this.root === null) {
return false;
}
let currentNode: BSTNode | null = this.root;
let parentNode: BSTNode | null = null;
while (currentNode !== null) {
parentNode = currentNode;
if (value < currentNode.value) {
currentNode = currentNode.left;
} else if (value > currentNode.value) {
currentNode = currentNode.right;
} else {
if (!currentNode.left && !currentNode.right) {
if (parentNode) {
if (currentNode.value > parentNode.value) {
parentNode.right = null;
} else {
parentNode.left = null;
}
}
} else {
// let's get the successor node
let possibleSuccessorNode = currentNode;
let foundLeft = false;
do {
if (possibleSuccessorNode.left) {
possibleSuccessorNode = possibleSuccessorNode.left;
foundLeft = true;
} else if (possibleSuccessorNode.right) {
possibleSuccessorNode = possibleSuccessorNode.right;
foundLeft = false;
} else {
break;
}
} while (possibleSuccessorNode !== null);
if (possibleSuccessorNode) {
if (foundLeft) {
currentNode.left = null;
} else {
currentNode.right = null;
}
currentNode.value = possibleSuccessorNode.value;
}
}
}
}
}
}
const tree = new BinarySearchTree();
tree.insert(9);
tree.insert(4);
tree.insert(6);
tree.insert(20);
tree.insert(170);
tree.insert(15);
tree.insert(1);
console.log(JSON.stringify(traverse(tree.root)));
// tree.remove(170);
tree.remove(20);
tree.remove(123);
console.log('After remove', JSON.stringify(traverse(tree.root)));
console.log(tree.lookup(20));
console.log(tree.lookup(21));
// 9
// 4 20
// 1 6 15 170
function traverse(node?: BSTNode | null): BSTNode | null {
if (!node) return null;
const tree: BSTNode = { value: node.value, left: null, right: null };
tree.left = node.left === null ? null : traverse(node.left);
tree.right = node.right === null ? null : traverse(node.right);
return tree;
}
TypeScript
INFO