BST

class BSTNode {
  public left: BSTNode | null;
  public right: BSTNode | null;
  public value: number;

  constructor(value: number) {
    this.left = null;
    this.right = null;
    this.value = value;
  }
}

class BinarySearchTree {
  public root: BSTNode | null;

  constructor() {
    this.root = null;
  }

  insert(value: number) {
    if (this.root === null) {
      this.root = new BSTNode(value);
    } else {
      const newNode = new BSTNode(value);
      let currentNode = this.root;

      while (currentNode !== null) {
        if (value < currentNode.value) {
          if (currentNode.left === null) {
            currentNode.left = newNode;
            break;
          }

          currentNode = currentNode.left;
        } else {
          if (currentNode.right === null) {
            currentNode.right = newNode;
            break;
          }

          currentNode = currentNode.right;
        }
      }
    }
  }

  lookup(value: number) {
    if (this.root === null) {
      return false;
    }

    let currentNode: BSTNode | null = this.root;

    while (currentNode !== null) {
      if (value === currentNode.value) {
        return true; // Value found
      }

      if (value < currentNode.value) {
        currentNode = currentNode.left;
      } else {
        currentNode = currentNode.right;
      }
    }

    return false; // Value not found
  }

  remove(value: number) {
    if (this.root === null) {
      return false;
    }

    let currentNode: BSTNode | null = this.root;
    let parentNode: BSTNode | null = null;

    while (currentNode !== null) {
      parentNode = currentNode;

      if (value < currentNode.value) {
        currentNode = currentNode.left;
      } else if (value > currentNode.value) {
        currentNode = currentNode.right;
      } else {
        if (!currentNode.left && !currentNode.right) {
          if (parentNode) {
            if (currentNode.value > parentNode.value) {
              parentNode.right = null;
            } else {
              parentNode.left = null;
            }
          }
        } else {
          // let's get the successor node
          let possibleSuccessorNode = currentNode;
          let foundLeft = false;

          do {
            if (possibleSuccessorNode.left) {
              possibleSuccessorNode = possibleSuccessorNode.left;
              foundLeft = true;
            } else if (possibleSuccessorNode.right) {
              possibleSuccessorNode = possibleSuccessorNode.right;
              foundLeft = false;
            } else {
              break;
            }
          } while (possibleSuccessorNode !== null);

          if (possibleSuccessorNode) {
            if (foundLeft) {
              currentNode.left = null;
            } else {
              currentNode.right = null;
            }
            currentNode.value = possibleSuccessorNode.value;
          }
        }
      }
    }
  }
}

const tree = new BinarySearchTree();
tree.insert(9);
tree.insert(4);
tree.insert(6);
tree.insert(20);
tree.insert(170);
tree.insert(15);
tree.insert(1);
console.log(JSON.stringify(traverse(tree.root)));
// tree.remove(170);
tree.remove(20);
tree.remove(123);
console.log('After remove', JSON.stringify(traverse(tree.root)));
console.log(tree.lookup(20));
console.log(tree.lookup(21));
//      9
//   4     20
// 1  6  15  170

function traverse(node?: BSTNode | null): BSTNode | null {
  if (!node) return null;

  const tree: BSTNode = { value: node.value, left: null, right: null };
  tree.left = node.left === null ? null : traverse(node.left);
  tree.right = node.right === null ? null : traverse(node.right);

  return tree;
}