Binary Search Tree

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

class BinarySearchTree {
    constructor() {
        this.root = null;
    }
    
    insert(value) {
        let node = new Node(value);
        if (this.root === null) {
            this.root = node;
            return this;
        }
        
        let curr = this.root;
        while(curr !== null) {
            if (value > curr.value) {
                if (curr.right) {
                    curr = curr.right;    
                } else {
                    curr.right = node;
                    return;
                }
            } else {
                if (curr.left) {
                    curr = curr.left;    
                } else {
                    curr.left = node;
                    return;
                }
            }
        }
    }
    
    lookup(value) {
        if (this.root === null) {
            return null;
        }
        
        let curr = this.root;
        while (curr !== null ) {
            if (value > curr.value) { // go right
                if (curr.right) {
                    curr = curr.right;
                } else {
                    return null;
                }
            } else if( value < curr.value) { // go left, ie value is less than curr.value
                if (curr.left) {
                    curr = curr.left;
                } else {
                    return null;
                }
            } else { // if value == curr.value
                return curr;
            }
        }
    }
    
    remove(value) {
        if (this.root === null) {
            return null;
        }
        
        let parent = this.root;
        let curr = this.root;
        let left = this.root.left;
        let right = this.root.right;
        while (curr !== null ) {
            console.log(curr.value);
            if (value > curr.value) {
                console.log("going right");
                parent = curr;
                curr = curr.right;
                left = curr.left;
                right = curr.right;
            } else if (value < curr.value) {
                console.log("going left");
                parent = curr;
                curr = curr.left
                left = curr.left;
                right = curr.right;
            } else if (curr.value === value) {
                if (curr.left === null && curr.right === null) { // leaf node
                    if (value < parent.value) {
                        parent.left = null;
                    } else {
                        parent.right = null;
                    }
                    return curr;
                }
                
                if (curr.right.left === null && curr.right.right === null) {
                    parent.right = curr.right;
                    parent.right.left = left;
                    return curr;
                }
                
                if (curr.right.left === null && curr.right.right !== null) {
                    parent.right = curr.right;
                    parent.right.left = left;
                    return curr;
                }
                
                if (curr.right.left !== null && curr.right.right === null) {
                    parent.right = curr.right.left;
                    parent.right.right = curr.right;
                    parent.right.left = curr.left;
                    curr.right.left = null;
                }
                
                curr = null;
            }
        }
        
    }
}

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

const tree = new BinarySearchTree();
tree.insert(9);
tree.insert(4);
tree.insert(20);
tree.insert(1);
tree.insert(15);
tree.insert(170);
tree.insert(6);
// tree.insert(180);
// tree.insert(179);
// tree.insert(181);
tree.insert(150);
console.log(tree.remove(20));
console.log(JSON.stringify(traverse(tree.root)));