My code was Accepted but I used Long.MAX_VALUE and Long.MIN_VALUE. How can I get rid of it?


  • 0
    X
    public boolean isValidBST(TreeNode root) {
        if(root==null)
            return true;
            
        return check(root, Long.MAX_VALUE, Long.MIN_VALUE); //How can I get rid of this????
    
    }
    
    public boolean check(TreeNode node, long max, long min )
    {
        long limit = node.val;
        if(node.left!=null)
        {
            if(node.left.val>=limit || node.left.val<=min)
                return false;
        }
        if(node.right!=null)
        {
            if(node.right.val<=limit  || node.right.val>=max)
                return false;
        }
        if(node.right!=null && node.left!=null)
            return check(node.left, node.val, min) && check(node.right, max, node.val);
        else if(node.right!=null && node.left==null)
            return check(node.right, max, node.val);
        else if(node.right==null && node.left!=null)
            return check(node.left, node.val, min);
        else
            return true;
    }
    

    Can anyone help me with this? I don't want to use MAX_VALUE or MIN_VALUE of long. It was accepted bc the test case doesn't have Long.MAX_VALUE. it does have Integer.MAX_VALUE so I changed it to Long. Any thoughts would be greatly appreciated!


  • 0
    A

    @XiSmartElf I also stumbled upon same issue. If you use this algorithm then you have to pass a maximum value and minimum value and it will fail for test case where treenode includes these values.

    Other alternative is to use following algo.

       TreeNode prev = null;
    public boolean isValidBST(TreeNode root){
    	if(root!=null){
    		if(!isValidBST(root.left))
    			return false;
    		if(prev!=null && prev.val>=root.val)
    			return false;
    		prev = root;
    		if(!isValidBST(root.right))
    			return false;
    	}
    	return true;
    }
     }
    

  • 0
    W

    if I reuse the Solution object, then prev is not able to work correctly


  • 0
    A

    @wenlong3 - What do you mean by that? For the given problem it works correctly. And why do you need to reuse solution object?


  • 0
    G

    I think you may use compareTo() method of Integer, like this AC code:

    public class Solution {
        public boolean isValidBST(TreeNode root) {
            return valid(root, null, null);
        }
        
        private boolean valid(TreeNode root, Integer lo, Integer hi) {
            if (root == null) return true;
            
            Integer val = root.val;
            if (lo != null && val.compareTo(lo) <= 0) return false;
            if (hi != null && val.compareTo(hi) >= 0) return false;
                
            return valid(root.left, lo, val) && valid(root.right, val, hi);
            
        }
    }
    

    I think this approach is more general while writing ones own BST implementation in which we use generic Key's compareTo() method.


  • 0
    X

    so if it's null it's going to assume the value of null is infinite small?


  • 0
    G

    being null means there is no constraint on the corresponding side, which could definitely be regarded as negative or positive infinite.


Log in to reply
 

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