class Node {
  constructor(data, left = null, right = null) {
    this.data = data;
    this.left = left;
    this.right = right;
  }
}

class BST {
  constructor() {
    this.root = null;
  }
  add(data) {
    const node = this.root;
    if (node === null) {
      this.root = new Node(data);
      return;
    } else {
      const searchTree = function (node) {
        if (data < node.data) {
          if (node.left === null) {
            node.left = new Node(data);
            return;
          } else if (node.left !== null) {
            return searchTree(node.left);
          }
        } else if (data > node.data) {
          if (node.right === null) {
            node.right = new Node(data);
            return;
          } else if (node.right !== null) {
            return searchTree(node.right);
          }
        } else {
          return null;
        }
      };
      return searchTree(node);
    }
  }

  findMin() {
    let current = this.root;
    while (current.left !== null) {
      current = current.right;
    }
    return current.data;
  }

  findMax() {
    let current = this.root;
    while (current.right !== null) {
      current = current.right;
    }
    return current.data;
  }

  find(data) {
    let current = this.root;
    while (current.data !== data) {
      if (data < current.data) {
        current = current.left;
      } else {
        current = current.right;
      }
      if (current === null) {
        return null;
      }
    }
    return current;
  }

  isPresent(data) {
    let current = this.root;
    while (current) {
      if (data === current.data) {
        return true;
      }
      if (data < current.data) {
        current = current.left;
      } else {
        current = current.right;
      }
    }
    return false;
  }
  remove(data) {
    const findAndRemoveNode = function (startingNode, data) {
      if (startingNode === null) {
        return null;
      }
      if (data === startingNode.data) {
        if (startingNode.left === null && startingNode.right === null) {
          return null;
        }
        if (startingNode.left === null) {
          return startingNode.right;
        }
        if (startingNode.right === null) {

          return startingNode.right; 
        }
        let tempNode = startingNode.right;
        while (tempNode.left !== null) {
          tempNode = tempNode.left;
        }
        startingNode.data = tempNode.data;
        startingNode.right = findAndRemoveNode( 
          startingNode.right,
          tempNode.data
        );
        return startingNode;
      } else if (data < startingNode.data) {
        startingNode.left = findAndRemoveNode(startingNode.left, data);
        return startingNode;
      } else {
        startingNode.right = findAndRemoveNode(startingNode.right, data);
        return startingNode;
      }
    };
    this.root = findAndRemoveNode(this.root, data);
  }
}