BinarySearchTree

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

class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  insert(value, parent) {
    const node = new Node(value);
    if (!this.root) {
      this.root = node;
      return;
    } else {
      if (!parent) {
        parent = this.root;
      }
      let nextNode = null;
      if (value > parent.value) {
        nextNode = parent.right;
        if (nextNode) {
          this.insert(value, nextNode);
        } else {
          parent.right = node;
          return;
        }
      } else {
        nextNode = parent.left;
        if (nextNode) {
          this.insert(value, nextNode);
        } else {
          parent.left = node;
          return;
        }
      }
    }
  }

  lookup(value, parent) {
    if (!parent) {
      parent = this.root;
    }
    if (parent.value === value) {
      return true;
    }
    let nextNode = null;
    if (value > parent.value) {
      nextNode = parent.right;
      if (nextNode) {
        return this.lookup(value, nextNode);
      } else {
        return false;
      }
    } else {
      nextNode = parent.left;
      if (nextNode) {
        return this.lookup(value, nextNode);
      } else {
        return false;
      }
    }
  }

  remove(value) {
    // TODO: I test few test and it worked but i am not sure it'll work for other inputs
    let currentNode = this.root;
    let nextNode = null;
    let nextLeftNode = null;
    while (currentNode) {
      if (value > currentNode.value) {
        nextNode = currentNode.right;
        if (nextNode && nextNode.value === value) {
          if (!nextNode.right) {
            currentNode.right = null;
          } else {
            let leafNode = nextNode.right;
            let parentOfLeaf = nextNode;
            let pointerNode = nextNode.right;
            while (pointerNode) {
              parentOfLeaf = leafNode;
              leafNode = pointerNode;
              pointerNode = leafNode.left;
            }
            console.log("#####", leafNode, parentOfLeaf);
            if (!leafNode) {
              nextLeftNode = nextNode.left;
              leafNode = nextNode.right;
            }
            let leafNodeRight = leafNode.right;
            currentNode.right = leafNode;
            parentOfLeaf.left = leafNodeRight;
            currentNode.right.right = nextNode.right;
            currentNode.right.left = nextNode.left;
            if (nextLeftNode) {
              currentNode.right.left = nextLeftNode;
            }
          }
          return;
        } else {
          currentNode = currentNode.right;
        }
      } else if (value < currentNode.value) {
        nextNode = currentNode.left;
        if (nextNode && nextNode.value === value) {
          if (!nextNode.right) {
            currentNode.left = null;
          } else {
            let leafNode = nextNode.right.left;
            let parentOfLeaf = nextNode;
            let pointerNode = nextNode.right;
            while (leafNode) {
              leafNode = pointerNode;
              pointerNode = leafNode.left;
            }
            if (!leafNode) {
              nextLeftNode = nextNode.left;
              leafNode = nextNode.right;
            }
            let leafNodeRight = leafNode.right;
            currentNode.left = leafNode;
            parentOfLeaf.right = leafNodeRight;
            // currentNode.left.right = ;
            // currentNode.left.left = nextNode.left;
            if (nextLeftNode) {
              currentNode.left.left = nextLeftNode;
            }
          }
          return;
        } else {
          currentNode = currentNode.left;
        }
      } else if (value === currentNode.value) {
        console.log(currentNode);
        return true;
      }
    }
    return false;
  }
}

const binarySearchTree = new BinarySearchTree();

console.log(binarySearchTree);

[41, 20, 74, 11, 29, 50, 91, 32, 80, 99, 75, 81, 92, 76].forEach((item) => {
  binarySearchTree.insert(item);
});

console.log(binarySearchTree.lookup(21));
console.log(binarySearchTree.lookup(23));
console.log(binarySearchTree.lookup(9));
console.log(binarySearchTree.remove(74));
console.log(binarySearchTree.remove(75));
console.log(binarySearchTree.remove(20));

console.log(JSON.stringify(binarySearchTree, null, 2));