Question about the expected in "Valid Binary Search Tree"


  • 0
    W
        public boolean isValidBST(TreeNode root) {
        boolean isValid = false;
        if(root == null)
            return true;
            
        boolean leftIs = false;
        boolean rightIs = false;
        if (root.left != null)
        {
            if(root.val > root.left.val)
                leftIs = isValidBST(root.left);
        }
        else
            leftIs = true;
            
        if(root.right != null)
        {
            if(root.val < root.right.val)
                rightIs = isValidBST(root.right);
        }
        else
            rightIs = true;
            
        if(leftIs == true && rightIs == true)
            isValid = true;
        
        return isValid;
        
    }
    

    The judge about the program is shown as below:

    Input: {10,5,15,#,#,6,20}
    Output: true
    Expected: false

    I do think that the tree should be a BST according to the Input, but the expected is false, which confusing. Could someone help me figure that out?


  • 0
    J

    6 is at the wrong position because it is bigger than 10.

    Assume a BST is defined as follows:

    • The entire left subtree of a node contains only nodes with values less than the node's value.
    • The entire right subtree of a node contains only nodes with values greater than the node's value.
    • Both the left and right subtrees must also be binary search trees.

Log in to reply
 

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