Detecting if a binary tree is a Binary Seach Tree: Java implementation

Hello Friends,

Today I am with you with another algorithm. Its about detecting if a Binary tree is a BST or not. A regular binary tree is a tree for which each node has number of children equal to 0, 1 or 2. A binary search tree has same properties as of regular binary tree with an additional property according to which any node has data  smaller than the data in its right child and greater data than the data in its left child.


We have two binary trees below.







Friends Lets look at the Java implementation solving this problem statement.

[Note that tree[] holds actual tree node values, left[] holds the index in tree[] corresponding to the left child of the each index and right[] holds the index in tree[] corresponding to the right child of the each index]

public class BSTDetector {
    // tree holds actual tree node values
    Integer tree[];
    // holds the index in tree[] corresponding to the left child of the each index
    Integer left[];
    // holds the index in tree[] corresponding to the right child of the each index
    Integer right[];

    public boolean isBinaryTreeBST(Integer tree[], Integer left[], Integer right[]) {
        this.tree = tree;
        this.left = left;
        this.right = right;
        return detectBST(Integer.MIN_VALUE, Integer.MAX_VALUE, 0);
    }

    private boolean detectBST(int leftRange, int rightRange, int currentIndex) {
        boolean isLeftChildvalid = true;
        boolean isRightChildValid = true;
        if (left[currentIndex] != null) {
            isLeftChildvalid = tree[currentIndex] >= tree[left[currentIndex]];
        }
        if (right[currentIndex] != null) {
            isRightChildValid = tree[currentIndex] <= tree[right[currentIndex]];
        }
        boolean isInRange = leftRange <= tree[currentIndex] && tree[currentIndex] <= rightRange;
        if (!isRightChildValid || !isLeftChildvalid || !isInRange) {
            return false;
        }
        boolean isLeftTreeBST = true;
        boolean isRightTreeBST = true;
        if (left[currentIndex] != null) {
            isLeftTreeBST = detectBST(leftRange, tree[currentIndex], left[currentIndex]);
        }
        if (right[currentIndex] != null) {
            isRightTreeBST = detectBST(tree[currentIndex], rightRange, right[currentIndex]);
        }

        return isLeftTreeBST && isRightTreeBST;
    }

    public static void main(String[] args) {
        Integer tree[] = { 10, 8, 6, 22, 12, 14 };
        Integer left[] = { 1, null, null, null, null, 2 };
        Integer right[] = { 4, null, null, null, 5, 3 };
        BSTDetector bstDetector = new BSTDetector();
        boolean isBST = bstDetector.isBinaryTreeBST(tree, left, right);
        System.out.println(isBST);

        Integer anotherInputTree[] = { 10, 8, 14, 22, 12, 15 };
        Integer anotherInputLeft[] = { 1, null, null, null, null, 2 };
        Integer anotherInputRight[] = { 4, null, null, null, 5, 3 };
        isBST = bstDetector.isBinaryTreeBST(anotherInputTree, anotherInputLeft, anotherInputRight);
        System.out.println(isBST);
    }
}