Binary Search Tree

A Binary Search Tree (BST) is a data structure in which each node has at most two children and maintains the property that for every node, the values in its left subtree are less than the node’s value, and the values in its right subtree are greater.

/**
 * @file Binary Search Tree
 * @author Dustin Boston
 * @see Cormen, T, Leiserson, C, Rivest, R, and Stein, C. (2001).
 *   Introduction to Algorithms. (2nd ed). The MIT Press.
 */

/**
 * Represents a node in a binary search tree.
 *
 * @template KeyType The type of the key stored in the node.
 */
class BinarySearchTreeNode<KeyType> {
  /**
   * Creates an instance of a binary search tree node.
   *
   * @param key The key associated with the node.
   * @param leftChildNode A reference to the left child of the node.
   * @param rightChildNode A reference to the right child of the node.
   * @param parentNode A reference to the parent of the node.
   */
  constructor(
    public key: KeyType,
    public leftChildNode?: BinarySearchTreeNode<KeyType>,
    public rightChildNode?: BinarySearchTreeNode<KeyType>,
    public parentNode?: BinarySearchTreeNode<KeyType>,
  ) {}
}

/**
 * Implements a generic binary search tree.
 *
 * @template KeyType The type of the keys stored in the tree.
 */
class BinarySearchTree<KeyType> {
  /**
   * Initializes a new instance of the BinarySearchTree class.
   *
   * @param rootNode The root node of the tree. It defaults to undefined.
   */
  constructor(public rootNode?: BinarySearchTreeNode<KeyType>) {}

/**
   * Performs an in-order traversal of the tree, executing a function on each
   * node's key.
   *
   * @param startingNode The starting node of the traversal.
   */
  inorderTreeWalk(startingNode?: BinarySearchTreeNode<KeyType>): void {
    if (startingNode !== undefined) {
      this.inorderTreeWalk(startingNode.leftChildNode);
      console.log(startingNode.key);
      this.inorderTreeWalk(startingNode.rightChildNode);
    }
  }

/**
   * Recursively searches for a node with a given key.
   *
   * @param keyToFind The key to search for in the tree.
   * @param startingNode The node to start the search from.
   * @returns The node containing the key, or undefined if not found.
   */
  treeSearch(
    keyToFind: KeyType,
    startingNode?: BinarySearchTreeNode<KeyType>,
  ): BinarySearchTreeNode<KeyType> | undefined {
    if (startingNode === undefined || keyToFind === startingNode.key) {
      return startingNode;
    }

if (keyToFind < startingNode.key) {
      return this.treeSearch(keyToFind, startingNode.leftChildNode);
    }

return this.treeSearch(keyToFind, startingNode.rightChildNode);
  }

/**
   * Iteratively searches for a node with a given key. This is an alternative to
   * the recursive search method. It is more efficient for large trees and
   * avoids stack overflow errors.
   *
   * @param keyToFind The key to search for.
   * @param startingNode The node to start the search from, or root if
   *   unspecified.
   * @returns The node containing the key, or undefined if not found.
   */
  iterativeTreeSearch(
    keyToFind: KeyType,
    startingNode?: BinarySearchTreeNode<KeyType>,
  ): BinarySearchTreeNode<KeyType> | undefined {
    while (startingNode !== undefined && keyToFind !== startingNode.key) {
      startingNode =
        keyToFind < startingNode.key
          ? startingNode.leftChildNode
          : startingNode.rightChildNode;
    }

return startingNode;
  }

/**
   * Finds the node with the minimum key in the subtree rooted at the given
   * node.
   *
   * @param startingNode The root node of the subtree.
   * @returns The node with the smallest key in the subtree.
   */
  getMinimum(
    startingNode: BinarySearchTreeNode<KeyType>,
  ): BinarySearchTreeNode<KeyType> {
    while (startingNode.leftChildNode !== undefined) {
      startingNode = startingNode.leftChildNode;
    }

return startingNode;
  }

/**
   * Finds the node with the maximum key in the subtree rooted at the given
   * node.
   *
   * @param startingNode The root node of the subtree.
   * @returns The node with the largest key in the subtree.
   */
  getMaximum(
    startingNode: BinarySearchTreeNode<KeyType>,
  ): BinarySearchTreeNode<KeyType> {
    while (startingNode.rightChildNode !== undefined) {
      startingNode = startingNode.rightChildNode;
    }

return startingNode;
  }

/**
   * Finds the successor of a given node in the in-order traversal of the tree.
   *
   * @param startingNode The node whose successor is to be found.
   * @returns The successor node if it exists, or undefined.
   */
  getSuccessor(
    startingNode: BinarySearchTreeNode<KeyType>,
  ): BinarySearchTreeNode<KeyType> | undefined {
    if (startingNode.rightChildNode !== undefined) {
      return this.getMinimum(startingNode.rightChildNode);
    }

let parentOfStartingNode = startingNode.parentNode;
    while (
      parentOfStartingNode !== undefined &&
      startingNode === parentOfStartingNode.rightChildNode
    ) {
      startingNode = parentOfStartingNode;
      parentOfStartingNode = parentOfStartingNode.parentNode;
    }

return parentOfStartingNode;
  }

/**
   * Inserts a new node into the binary search tree.
   *
   * @param newNode The new node to be inserted.
   * @returns The node that was inserted.
   */
  insertNode(
    newNode: BinarySearchTreeNode<KeyType>,
  ): BinarySearchTreeNode<KeyType> {
    let parentNode: BinarySearchTreeNode<KeyType> | undefined;
    let currentNode: BinarySearchTreeNode<KeyType> | undefined = this.rootNode;
    while (currentNode !== undefined) {
      parentNode = currentNode;
      currentNode =
        newNode.key < currentNode.key
          ? currentNode.leftChildNode
          : currentNode.rightChildNode;
    }

newNode.parentNode = parentNode;
    if (parentNode === undefined) {
      this.rootNode = newNode;
    } else if (newNode.key < parentNode.key) {
      parentNode.leftChildNode = newNode;
    } else {
      parentNode.rightChildNode = newNode;
    }

return newNode;
  }

/**
   * Deletes a node from the binary search tree.
   *
   * @param nodeToDelete The node to be deleted.
   * @returns The node that was removed from the tree, or undefined.
   */
  deleteNode(
    nodeToDelete: BinarySearchTreeNode<KeyType>,
  ): BinarySearchTreeNode<KeyType> | undefined {
    const successorNode: BinarySearchTreeNode<KeyType> | undefined =
      this.getSuccessor(nodeToDelete) ?? nodeToDelete;

const childNode: BinarySearchTreeNode<KeyType> | undefined =
      successorNode.leftChildNode ?? successorNode.rightChildNode;

if (childNode !== undefined && successorNode.parentNode !== undefined) {
      childNode.parentNode = successorNode.parentNode;
    }

if (successorNode.parentNode === undefined) {
      this.rootNode = childNode;
    } else if (successorNode === successorNode.parentNode.leftChildNode) {
      successorNode.parentNode.leftChildNode = childNode;
    } else {
      successorNode.parentNode.rightChildNode = childNode;
    }

if (successorNode !== nodeToDelete) {
      nodeToDelete.key = successorNode.key;
    }

return successorNode;
  }
}

// Usage
(() => {
  const bst = new BinarySearchTree<number>();

const node2 = bst.insertNode(new BinarySearchTreeNode(2));
  const node3 = bst.insertNode(new BinarySearchTreeNode(3));
  const node8 = bst.insertNode(new BinarySearchTreeNode(8));

if (!bst.rootNode) {
    throw new Error('Root should be defined.');
  }

const result = bst.treeSearch(8, bst.rootNode);
  if (result !== node8) {
    throw new Error(
      `Expected search to return node 8, got ${result?.key ?? 'undefined'}.`,
    );
  }

console.log('Found node:', result.key);

const maximumNode = bst.getMaximum(bst.rootNode);
  if (maximumNode !== node8) {
    throw new Error('Maximum should be 8.');
  }

console.log('Maximum node:', maximumNode.key);

const minimumNode = bst.getMinimum(bst.rootNode);
  if (minimumNode !== node2) {
    throw new Error('Minimum should be 2.');
  }

console.log('Minimum node:', minimumNode.key);

const deletedNode = bst.deleteNode(node3);
  const undefinedSearchResult = bst.treeSearch(3, bst.rootNode);
  if (deletedNode === undefined || undefinedSearchResult !== undefined) {
    throw new Error('Node 3 was not deleted.');
  }

console.log('Deleted node:', deletedNode.key);
})();