Binary Search Tree

bts.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;
  }
}

bts_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();
  });
});