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