Binary search tree algorithm implemented in TypeScript

binary tree illustration

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);

Discover more from Alper Yildirim

Subscribe to get the latest posts to your email.

Leave a Reply

Your email address will not be published. Required fields are marked *