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?

CodePudding user response：

A cleaner recursive approach

You could use a bounded approach, i.e. have two variables for every recursion: min and max.

• Initially min = INT_MIN and max = INT_MAX

• if node = NULL then return True because an empty BST is a BST

• else check if node.val < min or node.val > max if this condition is True then tree is not a BST, return False Notice : the strict inequality > and < are used as BST doesn't allow duplicate elements.

• recurse for left : recur(node.left) with min remaining the same and max = node.val - 1 because the left subtrees should have values not greater than node.val - 1.

  The max cannot be node.val because BST cannot have duplicate elements. Store the boolean return value in say left

• recurse for right : recur(node.right) with min = node.val 1 and max remaining the same.

  The right subtrees should have values not less than node.val 1. Store the boolean return value in say right

• return left && right

CodePudding user response：

@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);           
}