Binary Search Tree

class TreeNode {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}
class BST {
    constructor(value) {
        if(typeof value !== "undefined") {
            this.root = new TreeNode(value);
        }else {
            this.root = null;
        }
    }
    insert(value) {
        if(this.root === null) {
            this.root = new TreeNode(value);
        }else {
            let cur = this.root;
            while(cur !== null) {
                if(value >= cur.value) {
                    if(cur.right === null) {
                        cur.right = new TreeNode(value);
                        return this;
                    }else {
                        cur = cur.right;
                    }
                }else {
                    if(cur.left === null) {
                        cur.left = new TreeNode(value);
                        return this;
                    }else {
                        cur = cur.left;
                    }
                }
            }
        }
        return this;
    }
    lookup(value) {
        if(this.root === null) {
            return false;
        }else {
            let cur = this.root;
            while(cur !== null) {
                if(value === cur.value) {
                    return cur;
                }else if(value > cur.value) {
                    cur = cur.right;
                }else {
                    cur = cur.left;
                }
            }
            return false;
        }
    }
    removeNode(value) {
        if(this.root === null) {
            return false;
        }else {
            if(this.root.value === value) {
                const sucNode = this.getSuccessor(this.root);
                if(sucNode !== null) {
                    sucNode.left = this.root.left;
                    sucNode.right = this.root.right;
                }
                this.root = sucNode;
                return this;
            }else {
                let cur = this.root;
                while(cur !== null) {
                    if(value === cur.left) {
                        const sucNode = this.getSuccessor(cur.left);
                        if(sucNode !== null) {
                            sucNode.left = cur.left.left;
                            sucNode.right = cur.left.right;
                        }
                        cur.left = sucNode;
                        return this;
                    }else if(value === cur.right) {
                        const sucNode = this.getSuccessor(cur.right);
                        if(sucNode !== null) {
                            sucNode.left = cur.right.left;
                            sucNode.right = cur.right.right;
                        }
                        cur.right = sucNode;
                        return this;
                    }else if(value < cur.value) {
                        cur = cur.left;
                    }else {
                        cur = cur.right;
                    }
                }
                return false;
            }
        }
    }
    getSuccessor(node) {
        if(node.left === null) {
            if(node.right === null) {
                return null;
            }else {
                const temp = node.right;
                node.right = null;
                return temp;
            }
        }else if(node.right === null) {
            const temp = node.left;
            node.left = null;
            return temp;
        }else {
            if(node.right.left === null) {
                const temp = node.right;
                node.right = null;
                return temp;
            }else {
                let cur = node.right;
                while(cur.left.left !== null) {
                    cur = cur.left;
                }
                const temp = cur.left;
                cur.left = null
                return temp;
            }
        }
    }
    inOrderTraversal() {
        function trav(node) {
            if(node === null) {
                return null;
            }
            trav(node.left);
            console.log(node.value);
            trav(node.right);
        }
        trav(this.root);
    }
    breadthFirstSearchR() {
        if(this.root === null) {
            return null;
        }
        function trav(nodeQueue) {
            if(nodeQueue.length === 0) {
                return;
            }
            const node = nodeQueue.shift();
            console.log(node.value);
            if(node.left !== null) {
                nodeQueue.push(node.left);
            }
            if(node.right !== null) {
                nodeQueue.push(node.right);
            }
            return trav(nodeQueue);
        }
        const queue = [this.root];
        trav(queue);
    }
    breadthFirstSearchI() {
        if(this.root === null) {
            return null;
        }
        const nodeQueue = [this.root];
        while(nodeQueue.length > 0) {
            const node = nodeQueue.shift();
            console.log(node.value);
            if(node.left !== null) {
                nodeQueue.push(node.left);
            }
            if(node.right !== null) {
                nodeQueue.push(node.right);
            }
        }
    }
}

const bst1 = new BST(5);
bst1.insert(8);
bst1.insert(7);
bst1.insert(9);
bst1.insert(3);
bst1.insert(4);
bst1.insert(2);
bst1.inOrderTraversal();
console.log("BST Recursive");
bst1.breadthFirstSearchR();
console.log("BST Iterative");
bst1.breadthFirstSearchI();