Binary Search Tree | The Personal Website of Dustin Boston

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.

code.ts

/**
 * @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.
 */
export 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.
 */
export 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;
  }
}

test.ts

import {expect, test, describe} from "bun:test";
import {BinarySearchTree, BinarySearchTreeNode} from "./code.ts";

export function getTree() {
  const b = new BinarySearchTree<number>();

  const n2 = new BinarySearchTreeNode(2);
  const n3 = new BinarySearchTreeNode(3);
  const n8 = new BinarySearchTreeNode(8);

  b.insertNode(n3);
  b.insertNode(n8);
  b.insertNode(n2);

  return {b, n2, n3, n8};
}

describe("Binary Search Tree", () => {
  test("Insert", () => {
    const bst = getTree();
    const {b, n3, n8, n2} = bst;

    expect(b.rootNode).toBeDefined();
    expect(b.rootNode).toBe(n3);
    expect(b.rootNode?.leftChildNode).toBe(n2);
    expect(b.rootNode?.rightChildNode).toBe(n8);

    const n7 = new BinarySearchTreeNode(7);
    b.insertNode(n7);
    expect(b.rootNode?.rightChildNode?.leftChildNode).toBe(n7);
  });

  test("Search", () => {
    const bst = getTree();
    const {b, n8} = bst;

    expect(b.rootNode).toBeDefined();
    const result = b.treeSearch(8, b.rootNode);
    expect(result).toBe(n8);
    const iterativeResult = b.iterativeTreeSearch(8, b.rootNode);
    expect(iterativeResult).toBe(n8);
  });

  test("Min/Max", () => {
    const bst = getTree();
    const {b, n8, n2} = bst;

    expect(b.rootNode).toBeDefined();

    if (!b.rootNode) {
      throw new Error("Unexpected undefined root node.");
    }

    const maximumNode = b.getMaximum(b.rootNode);
    expect(maximumNode.key).toBe(n8.key); // Maximum key comparison
    const minimumNode = b.getMinimum(b.rootNode);
    expect(minimumNode.key).toBe(n2.key); // Minimum key comparison
  });

  test("Delete", () => {
    const bst = getTree();
    const {b, n2} = bst;

    expect(b.rootNode);

    const n7 = new BinarySearchTreeNode(7);
    b.insertNode(n7);
    expect(b.rootNode?.rightChildNode?.leftChildNode).toBe(n7);

    b.deleteNode(n7);
    expect(b.treeSearch(7, b.rootNode), undefined);

    const n1 = new BinarySearchTreeNode(1);
    b.insertNode(n1);
    b.deleteNode(n2);
    const result = b.treeSearch(2, b.rootNode);
    expect(result).toBeUndefined();
  });
});