Binary Search Tree

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

class BinarySearchTree {
    constructor() {
       this.root = null;
    }
    
    lookup(value){
        if (!this.root) return false;
        
        let currentNode = this.root;
        while(currentNode) {
            if(value < currentNode.value) {
                currentNode = currentNode.left;
            } else if(value > currentNode.value) {
                currentNode = currentNode.right;
            } else if (value === currentNode.value) {
                return currentNode;
            }
        }
        return false;
    }
    
    insert(value){
        const newNode =  new Node(value);
        
         if (!this.root) {
             this.root = newNode;
             return this;
         }
         
         let currentNode = this.root;
         while(true) {
             if (value < currentNode.value) {
                 //Left
                 if (!currentNode.left) {
                     currentNode.left = newNode;
                     return this;
                 }
                 
                 currentNode = currentNode.left;
                
             } else {
                 //Right
                 if (!currentNode.right) {
                     currentNode.right = newNode;
                     return this;
                 }
                 
                  currentNode = currentNode.right;
             }
         }
    }
    //wont see in interview
    remove(value) {
        if (!this.root) {
            return false;
        }
        
        let currentNode = this.root;
        let parentNode = null;
        
        while (currentNode) {
            if (value < currentNode.value) {
                parentNode = currentNode;
                currentNode = currentNode.left;
            } else if (value > currentNode.value) {
                parentNode = currentNode;
                currentNode = currentNode.right;
            } else if (currentNode.value === value) {
            //We have a match, get to work!
    
            //Option 1: No right child:
            if (!currentNode.right) {
                if (!parentNode) {
                    this.root = currentNode.left;
                 } else {
                    //if parent > current value, make current left child a child of parent
                    if (currentNode.value < parentNode.value) {
                        parentNode.left = currentNode.left;
    
                  //if parent < current value, make left child a right child of parent
                    } else if (currentNode.value > parentNode.value) {
                        parentNode.right = currentNode.left;
                    }
                }
    
              //Option 2: Right child which doesnt have a left child
            } else if (!currentNode.right.left) {
                currentNode.right.left = currentNode.left;
                if (!parentNode) {
                    this.root = currentNode.right;
                } else {
                    //if parent > current, make right child of the left the parent
                    if (currentNode.value < parentNode.value) {
                        parentNode.left = currentNode.right;
    
                    //if parent < current, make right child a right child of the parent
                    } else if (currentNode.value > parentNode.value) {
                        parentNode.right = currentNode.right;
                    }
                }
    
              //Option 3: Right child that has a left child
            } else {
                //find the Right child's left most child
                let leftmost = currentNode.right.left;
                let leftmostParent = currentNode.right;
                
                while (!leftmost.left) {
                    leftmostParent = leftmost;
                    leftmost = leftmost.left;
                }
    
                  //Parent's left subtree is now leftmost's right subtree
                  leftmostParent.left = leftmost.right;
                  leftmost.left = currentNode.left;
                  leftmost.right = currentNode.right;
        
                  if (!parentNode) {
                    this.root = leftmost;
                  } else {
                    if (currentNode.value < parentNode.value) {
                        parentNode.left = leftmost;
                    } else if (currentNode.value > parentNode.value) {
                        parentNode.right = leftmost;
                    }
                }
            }
            return true;
          }
        }
    }
}

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);

const traverse = (node) => {
    const tree = { value: node.value };
    
    tree.left = node.left === null ? null : traverse(node.left);
    tree.rigtht = node.right === null ? null : traverse(node.right);
    
    return tree;
};

console.log(JSON.stringify(traverse(tree.root)));