CODEWITHSUNDEEP
javabinary-search-tree
SJackson193
SJackson193

Reputation: 31

Having trouble with detection of whether this is a BST or not

Trying to run a recursive algorithm to find out if a certain tree is a BST(Binary search tree).

boolean checkBST(Node root) {
    boolean isBST = true;
    if(root == null){
        return false;
    }
    if(root.left != null){
        if( isLessThan(root.data, root.left.data) == false ) {
            isBST = false;
            return isBST;
        } else
            checkBST(root.left);
    }
    if(root.right != null){
        if(isGreaterThan(root.data, root.right.data) == false) {
            isBST = false;
            return isBST;
        } else
            checkBST(root.right);
    }
    return isBST;
}


boolean isLessThan(int value1, int value2){
    if(value2< value1){
        return true;
    } 
    return false;
}

boolean isGreaterThan(int value1, int value2){
    if(value1 < value2){
        return true;
    } else
        return false;
}

I'm not sure whats wrong with my algorithm. Any help?

Upvotes: 0

Views: 37

Answers (1)

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726489

The problem is that your implementation ignores return values of recursive invocations of the method:

checkBST(root.left);
...
checkBST(root.right);

Regardless of the return value, your code continues on. Instead, it should check the return value, and return false if the check of a subtree returned false:

if (!checkBST(root.left)) {
    return false;
}
...
if (!checkBST(root.right)) {
    return false;
}

Upvotes: 2

Related Questions