Javascript - O(n) Top Down Recursion


  • 0
    A
    /**
     * Definition for a binary tree node.
     * function TreeNode(val) {
     *     this.val = val;
     *     this.left = this.right = null;
     * }
     */
    /**
     * Javascript Solution
     * Time: O(n) , Space: O(n)
     * We check if the number is within our limits, we replace the limits as we recurse. 
     * @param {TreeNode} root
     * @return {boolean}
     */
    var isValidBST = function(root) {
        if(root === null)
            return true;
        //Watch out for negative number!    
        return valid(root, -Number.MAX_VALUE, Number.MAX_VALUE);
    };
    
    
    // Helper function checks if tree is within min and max limits
    var valid = function(node, minLimit, maxLimit){
        if(node === null) //base case
            return true
         // return false if limits are not met. 
        return (node.val < maxLimit && node.val > minLimit) && valid(node.left, minLimit, node.val) && valid(node.right, node.val, maxLimit)
    }
    

Log in to reply
 

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