Javascript - BruteForce O(n^2)


  • 0
    A
     * Time O(n^2), Space O(n) - Recursive stack space
     * @param {TreeNode} root
     * @return {boolean}
     */
    var isValidBST = function(root) {
        if(root == null){
            return true;
        }
        
        return isLessthan(root.left, root.val) && isMorethan(root.right, root.val) && isValidBST(root.left) && isValidBST(root.right)
     
    };
    
    //isLessthan takes in value and passes the same value along to do the comparison
    //@param {treenode}, {value}
    //@return {boolean} 
    var isLessthan = function(node, value){
        if(node === null){
            return true;
        }
        return (node.val < value) && isLessthan(node.right, value) && isLessthan(node.left, value);
    }
    
    //We could have used  a higher order function to remove redundant code
    //@param {treenode}, {value}
    //@return {boolean} 
    var isMorethan = function(node, value){
        if(node === null)
            return true
        return (node.val > value) && isMorethan(node.left, value) && isMorethan(node.right, value);
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.