This class defines a BinarySearchTree
with a value
property, a left
property representing the left subtree, and a right
property representing the right subtree. It also includes methods for inserting, searching, and removing elements from the tree, as well as methods for finding the minimum and maximum elements in the tree or a subtree.
class BinarySearchTree<T> {
value: T;
left: BinarySearchTree<T> | null;
right: BinarySearchTree<T> | null;
constructor(value: T) {
this.value = value;
this.left = null;
this.right = null;
}
// Insert a new element into the tree
insert(value: T) {
if (value < this.value) {
if (this.left) {
this.left.insert(value);
} else {
this.left = new BinarySearchTree(value);
}
} else {
if (this.right) {
this.right.insert(value);
} else {
this.right = new BinarySearchTree(value);
}
}
}
// Search for a value in the tree
search(value: T): BinarySearchTree<T> | null {
if (value < this.value) {
if (this.left) {
return this.left.search(value);
} else {
return null;
}
} else if (value > this.value) {
if (this.right) {
return this.right.search(value);
} else {
return null;
}
} else {
return this;
}
}
// Remove an element from the tree
remove(): BinarySearchTree<T> | null {
// Check if the node is a leaf
if (!this.left && !this.right) {
return null;
} else if (this.left && this.right) {
// The node has two children, find the next largest value
const successor = this.right.minimum();
this.value = successor.value;
successor.remove();
} else {
// Check if the node has only one child
if (this.left) {
return this.left;
} else {
return this.right;
}
}
return this;
}
// Find the node with the minimum value in the subtree
minimum(): BinarySearchTree<T> {
let node = this;
while (node.left) {
node = node.left;
}
return node;
}
// Find the node with the maximum value in the subtree
maximum(): BinarySearchTree<T> {
let node = this;
while (node.right) {
node = node.right;
}
return node;
}
}
You can use this class by creating a new BinarySearchTree
instance and calling its methods, like this:
const tree = new BinarySearchTree(10);
tree.insert(5);