Check if BST

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;
            }
        }
        
    }
    
    preorderTraversal(node, list) {
        list.push(node.value);
        if (node.left !== null) {
            this.preorderTraversal(node.left, list);
        }
        if (node.right !== null) {
            this.preorderTraversal(node.right, list);
        }
        return list;
    }
    
    postorderTraversal(node, list) {
        if (node.left !== null) {
            this.postorderTraversal(node.left, list);
        }
        if (node.right !== null) {
            this.postorderTraversal(node.right, list);
        }
        list.push(node.value);
        return list;
    }
    
    inorderTraversal(node, list) {
        if (node.left !== null) {
            this.inorderTraversal(node.left, list);
        }
        list.push(node.value);
        if (node.right !== null) {
            this.inorderTraversal(node.right, list);
        }
        return list;
    }
}


// Helper function to check if a tree is BST 
// within a given range
function isBSTUtil(node, min, max) {
    if (node === null) return true;

    // If the current node's data 
    // is not in the valid range, return false
    if (node.data < min || node.data > max) return false;

    // Recursively check the left and 
    // right subtrees with updated ranges
    return isBSTUtil(node.left, min, node.data - 1) &&
           isBSTUtil(node.right, node.data + 1, max);
}

// Function to check if the entire binary tree is a BST
function isBST(root) {
    return isBSTUtil(root, -Infinity, Infinity);
}




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


if (isBST(tree.root)) {
    console.log("True");
} else {
    console.log("False");
}