Checking a tree to be a BST

Here is my attempt to check whether a tree is a BST or not:

public boolean isBST() {
    return isBSTRecursively(this.root, new Max());
}

class Max {
    int value;
}

private boolean isBSTRecursively(Node node, Max max) {
    if (node == null) return true; // to handle null root
  
    // to handle scenario when both child nodes are absent
    if(node.getLeft() == null && node.getRight() == null) {
        max.value = node.getValue();
        return true;
    }

    // if left child is absent, we only investigate right subtree
    if(node.getLeft() == null) {
        Max rightMax = new Max();
        boolean isRightBST = isBSTRecursively(node.getRight(), rightMax);
        max.value = Math.max(node.getValue(), rightMax.value);
        if(isRightBST && node.getValue() < rightMax.value) {
            return true;
        } else {
            return false;
        }
    } else {
        Max leftMax = new Max();
        boolean isLeftBST = isBSTRecursively(node.getLeft(), leftMax);
        // if right child is absent, we only investigate left subtree
        if(node.getRight() == null) {
            max.value = Math.max(node.getValue(), leftMax.value);
            if(isLeftBST && node.getValue() > leftMax.value) {
                return true;
            } else {
                return false;
            }
        } else {
            // we investigate both left and right subtrees
            Max rightMax = new Max();
            boolean isRightBST = isBSTRecursively(node.getRight(), rightMax);
            max.value = Math.max(Math.max(leftMax.value, node.getValue()), rightMax.value);
            if(isLeftBST && isRightBST && leftMax.value < node.getValue() && node.getValue() < rightMax.value) {
                return true;
            } else {
                return false;
            }
        }
    }

Code works fine as tested with multiple test cases.

But I am not sure if this is a good, clean approach.

Recursive method is big it seems. I am dealing with scenarios like null left node, null right node, node itself null, both child nodes null etc. separately. I guess they all can be handled in a much smaller, and cleaner way.

Moreover, I am always more inclined towards iterative approach(I generally find it better to visualize). Would that be better here (given it can be done iteratively)?

Any suggestions?

Answer

@Aditya gave the ingredients of the more elegant solution.

It is generally not forbidden for a binary search tree to have duplicate values, so there should no be reduction of the “window” with 1.

Here is suggested code:

public boolean isBST() {
    return isBSTRecursively(this.root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

private boolean isBSTRecursively(Node node, int min, int max) {
    return node == null
           || node.getValue() >= min && node.getValue() <= max
               && isBSTRecursively(node.getLeft(), min, node.getValue())
               && isBSTRecursively(node.getRight(), node.getValue(), max);           
}

Advertisement

Answer