Test cases missing


  • 11
    L

    There should be a test case where some nodes have values equal to Integer.MIN_VALUE and Integer.MAX_VALUE;

    This solution is accepted and shouldn't be:

    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        return isValidBST(root.left,Integer.MIN_VALUE, root.val) 
               && isValidBST(root.right,root.val,Integer.MAX_VALUE);
    }
    
    public boolean isValidBST(TreeNode root, int smallest, int largest) {
        if (root == null) return true;
        if (root.val > smallest && root.val < largest)
            return isValidBST(root.left,smallest, root.val) 
                   && isValidBST(root.right,root.val,largest);
        else
            return false;
    }

  • 6

    Yes, you are right. Adding test case which contains INT_MIN or INT_MAX means your code no longer works.

    I decided not to include these edge cases, as a good programmer should be able to pinpoint these edge cases and fix their code anyway. As a good followup question, can you modify your code to handle these edge cases?

    Update: I've strengthen the test cases to prevent code that relies on INT_MIN or INT_MAX from passing. Thanks for the feedback.


  • 0
    H

    is this right? or anyone has a better solution for min_value and max_value (except for Long.MAX_VALUE)

    public boolean isValidBST(TreeNode root) {
    	//initial that: meet MIN_VALUE = false and MAX_VALUE = false
        return validRSTRecursive(root,Integer.MIN_VALUE,Integer.MAX_VALUE,false,false);
    }
    public boolean validRSTRecursive(TreeNode node,int lower, int upper, boolean MinValueMeet, boolean MaxValueMeet) {
        if(node == null) {
            return true;
        }
        
        if(node.val == Integer.MIN_VALUE) {      //care about test case: node.val = MIN_VALUE
            if(MinValueMeet) {                   //can only meet MIN_VALUE once
            	return false;
            }
        	MinValueMeet = true;
        	//left node should be null and recursively to right tree
            return (node.left == null) && validRSTRecursive(node.right,node.val,upper,MinValueMeet,MaxValueMeet);
        }
        if(node.val == Integer.MAX_VALUE) {    //care about test case: node.val = MAX_VALUE
        	if(MaxValueMeet) {                 //can only meet MAX_VALUE once
            	return false;
            }
        	MaxValueMeet = true;
        	//right node should be null and recursively to left tree
            return (node.right == null) && validRSTRecursive(node.left,lower,node.val,MinValueMeet,MaxValueMeet);
        }
        
        //no meet MIN_VALUE or MAX_VALUE
        if(node.val > lower && node.val < upper ) {
            return validRSTRecursive(node.left,lower,node.val,MinValueMeet, true) && validRSTRecursive(node.right,node.val,upper, true,MaxValueMeet);
        } else {
            return false;
        }
    }

  • 0
    Y
    This post is deleted!

  • 0
    L

    //Recursive solution without using INT_MAX and INT_MIN

    //For the binary tree, only one left side path and one right side path use single bound.

    //All other branches use double bounds.

    class Solution {
    public:
        enum class flag {LOW, UPPER};
    
        //flag f indicates the value is lower or upper bound
        bool single_bound(TreeNode *node, flag f, int bound) { 
            if (node == NULL) return true;
            
            if (f == flag::LOW) {
                if (node->val <= bound) return false;
                return double_bound(node->left, bound, node->val) && single_bound(node->right, flag::LOW, node->val);
            } else if (f == flag::UPPER) {
                if (node->val >= bound) return false;
                return single_bound(node->left, flag::UPPER, node->val) && double_bound(node->right, node->val, bound);
            }
        }
        
        bool double_bound(TreeNode *node, int low, int upper) {
            if (node == NULL) return true;
            if (node->val >= upper || node->val <= low) return false;
            
            return double_bound(node->left, low, node->val) && double_bound(node->right, node->val, upper);
        }
        
        bool isValidBST(TreeNode *root) {
            if (root == NULL || root->left == NULL && root->right == NULL) return true;
            
            return single_bound(root->left, flag::UPPER, root->val) && single_bound(root->right, flag::LOW, root->val);
        }
    };

  • 0
    C

    Your solution seems not right.
    for example { 3, 2, #, 1, Integer.MIN_VALUE}
    your algorithm will return true, however, MIN_VALUE is out side of the range (2, 3), the result should be false.


  • 0
    H

    thx, your example points out my bug. I have fixed the bug as you can see in the code.

    return validRSTRecursive(node.left,lower,node.val,MinValueMeet, true) && validRSTRecursive(node.right,node.val,upper, true,MaxValueMeet);

    if there exists any problem, please let me know, thanks for your reply.


  • 0
    V

    I request you to add at least 1 such test case. I just came to discussion to check any shorter solution and was surprised to realize that my accepted solution was actually wrong. It will help us to take care of edge cases in future.


  • 0
    D

    I think we could simply use -Double.MAX_VALUE and Double.MAX_VALUE to trick the problem


  • 0
    J

    I don't think so. They are not edge cases if you do not rely on the type of numbers so much. And why will you want to know the minimum and maximum of integer but do not care about that? Although you are not good programmers, you must be careless programmers.


Log in to reply
 

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