Need help checking if a binary tree is a valid binary search tree in Java

Question

Here is my code:

    public boolean isBST() {
        return isBST(this.root);
    }

    private boolean isBST(BinaryNode<T> rootNode) {
        if (rootNode == null) {
            return false;
        }
        if (rootNode.isLeaf()) {
            return true;
        }
        T left = null;
        T right = null;

        if (rootNode.hasLeftChild()) {
            left = rootNode.getLeftChild().getData();
            if (left.compareTo(rootNode.getData()) < 0) {
                return this.isBST(rootNode.getLeftChild());
            }
            else {
                return false;
            }
        }
        if (rootNode.hasRightChild()) {
            right = rootNode.getRightChild().getData();
            if (right.compareTo(rootNode.getData()) > 0) {
                return this.isBST(rootNode.getRightChild());
            }
            else {
                return false;
            }
        }
        return true;
    }

This code works for simple binary trees, but it doesn't work for other ones. Such as if I have a tree like so:

It won't mark it false even thought it should since 2 is smaller than 3 and is in the wrong place. My code just checks the left child's left children, and the checks the right child's right children and not the inner children. What can I do to make this code work in the way that I wrote it? How can I modify it?

You should combine results from left-check and right-check, and then return. The fact that it is working with full binary trees, I think, is pure luck. — fatih, Nov 22 '19 at 00:21

score 0 · Answer 1 · answered Nov 22 '19 at 00:18

The bug is in the line

return this.isBST(rootNode.getLeftChild());

You must not exit the method just because the left part is checked (if it exists).

Instead of

if (left.compareTo(rootNode.getData()) < 0) {
        return this.isBST(rootNode.getLeftChild());
}
else {
    return false;
}

this should do the expected:

if (left.compareTo(rootNode.getData()) >= 0 ||
              !this.isBST(rootNode.getLeftChild()) {

    return false;
}

(For symmetry reasons you may also want to rewrite the right part check in a similar way, however this is not required. Your could would also work in its current form.)

score 0 · Answer 2 · answered Nov 22 '19 at 00:22

I think all you need to do is when you recursively look left and right only return if it's false

if (rootNode.hasLeftChild()) {
    left = rootNode.getLeftChild().getData();
    if (left.compareTo(rootNode.getData()) < 0) {
        boolean isValid = this.isBST(rootNode.getLeftChild());
        if (!isValid) {
           return false;
        }
    } else {
        return false;
    }
}
if (rootNode.hasRightChild()) {
    right = rootNode.getRightChild().getData();
    if (right.compareTo(rootNode.getData()) > 0) {
        boolean isValid = this.isBST(rootNode.getRightChild());
        if (!isValid) {
           return false;
        }
    } else {
        return false;
    }
}

return true

It looks like, at a quick look, the return is happening before the right side is checked. Slightly more succinct version that also supports duplicates appearing only on the right (if you want to allow duplicates on the left then swap the >= in left comparison for <= in the right comparison

if (rootNode.hasLeftChild()) {
    left = rootNode.getLeftChild().getData();
    if (left.compareTo(rootNode.getData()) >= 0) || !this.isBST(rootNode.getLeftChild()) {
        return false;
    }
}

if (rootNode.hasRightChild()) {
    right = rootNode.getRightChild().getData();
    if (right.compareTo(rootNode.getData()) < 0 || !this.isBST(rootNode.getRightChild()) {
        return false;
    }
}

return true;

Need help checking if a binary tree is a valid binary search tree in Java

2 Answers2