c++ simple recursion, validate based on lower bound and upper bound


  • 0

    Boundaries need to be longs to allow INT_MIN and INT_MAX in the input tree.

    bool isValidBSTGivenBoundaries(TreeNode* root, long lowerBound, long upperBound) {
    	if (!root)
    		return true;
    	else
    		return root->val > lowerBound &&
                           root->val < upperBound &&
    		       isValidBSTGivenBoundaries(root->left, lowerBound, root->val) &&
    		       isValidBSTGivenBoundaries(root->right, root->val, upperBound);
    }
    
    bool isValidBST(TreeNode* root) {
    	if (!root)
    		return true;
    	else
    	    return isValidBSTGivenBoundaries(root->left, (long) INT_MIN-1, root->val) &&
                       isValidBSTGivenBoundaries(root->right, root->val, (long) INT_MAX+1);
    }
    

Log in to reply
 

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