const { NotImplementedError } = require('../extensions/index.js');

const { Node } = require('../extensions/list-tree.js');

/**
* Implement simple binary search tree according to task description
* using Node from extensions
*/
module.exports = class BinarySearchTree {
  constructor() {
    this._tree = null;
}

  root() {
    return this._tree;
  }


    add(data) {
      this._tree = addNode(this._tree, data);

      function addNode(node,data) {
          if (!node) {
              return new Node(data);
          }

          if (node.data === data) {
              return node.value
          }
          if (data < node.data) {
              node.left = addNode(node.left, data);
          }
          else {
          node.right = addNode(node.right, data);
          }
          return node;
          }
      }

  


  has(data) {
    return hasNode(this._tree, data);

    function hasNode(node,data) {

      if(!node) return false;

      if (node.data === data) return true;

      if (data < node.data) {
        return hasNode(node.left, data);
      }
      else {
        return hasNode(node.right, data);
      }
    }
  }
  find(data) {
    return findNode(this._tree, data);

    function findNode(node,data) {

      if(!node) return null;

      if (node.data === data) return node;

      if (data < node.data) {
        return findNode(node.left, data);
      }
      else {
        return findNode(node.right, data);
      }
    }
  }

  remove(data) {
    return removeNode(this._tree, data);

    function removeNode(node, data) {
        if (!node) {
            return null;
        }

        if (data < node.data) {
            node.left = removeNode(node.left, data);
            return node;
        } 
        else if (node.data <  data) {
            node.right = removeNode(node.right, data);
            return node;
        }
        else {
            if (!node.left && !node.right) {
                return null;
            }

            if (!node.left) {
                node = node.right;
                return node;
            }

            if (!node.right){
                node = node.left;
                return node;
            }
        
        
        let minFromRight = node.right;
        while (minFromRight.left) {
            minFromRight = minFromRight.left;
        }
        node.data = minFromRight.data;

        node.right = removeNode(node.right, minFromRight.data);

        return node;

      }
    }
  }
    
  min() {
    let node = this._tree;
    if(!node) {
      return null;
    }
    while (node.left) {
      node = node.left
    }
    return node.data;
  }
  max() {
    let node = this._tree;
    if(!node) {
      return null;
    }
    while (node.right) {
      node = node.right
    }
    return node.data;
  }
}