JAVA program to check whether a binary tree is an BST or not

ALGORITHM:

A binary search tree (BST) is a binary tree where each node has a Comparable key (and an associated value) and satisfies the restriction that the key in any node is larger than the keys in all nodes in that node's left subtree and smaller than the keys in all nodes in that node's right subtree.

So to check whether a binary tree is a binary search tree or not we just use a recursive function which passes the left and right subtrees and lower limit and upper limit of the value which the current node can have .

1. start with the root node with limits positive infinity and negative infinity
2. return true if reached the leaf
3. if the current node is legal then recurse the function by passing the left subtree and right subtree with limits passed lower limit argument and current node-1 as lower limit and upper limit for the left subtree and current node+1 and passed upper limit argument as lower limit and upper limit for right subtree.
4. return false if current node is illegal

CODE:

//utility class for node

public class node{
    public int data;
    public node left,right;
    public node(){
        data=0;
        left=right=null;
    }
}

//class to implement the algorithm

import java.util.Scanner;

class isBST{
    static Scanner in = new Scanner(System.in);
    static boolean isBSTree(node tree,int min,int max){
        if((tree==null)||((tree.left==null)&&(tree.right==null)))
            return true;
        if((tree.right==null)&&(tree.left.data<=max))
            return isBSTree(tree.left,min,tree.left.data-1);
        if((tree.left==null)&&(tree.right.data>=min))
            return isBSTree(tree.right,tree.right.data+1,max);
        if((tree.left.data<=max)&&(tree.right.data>=min))
            return isBSTree(tree.left,min,tree.left.data-1)&&isBSTree(tree.right,tree.right.data+1,max);
        return false;
    }

    static node inputTree(){
        node temp=new node();
        System.out.print("Enter the value: ");
        temp.data=in.nextInt();
        System.out.print("Enter y if the node "+temp.data+" has left subtree: ");
        if(in.next().charAt(0)=='y')
            temp.left=inputTree();
        else
            temp.left=null;
        System.out.print("Enter y if the node "+temp.data+" has right subtree: ");
        if(in.next().charAt(0)=='y')
            temp.right=inputTree();
        else
            temp.right=null;
        return temp;
    }

    static void inorder(node tree){
        if(tree==null)
            return;
        inorder(tree.left);
        System.out.print(tree.data+"\t");
        inorder(tree.right);
    }

    public static void main(String[] args) {
        node tree=new node();
        System.out.print("Enter y if tree is null: ");
        if(in.next().charAt(0)=='y')
            tree=null;
        else
            tree=inputTree();
        System.out.print("Inorder traversal of the tree is:\n");
        inorder(tree);
        if (isBSTree(tree,Integer.MIN_VALUE,Integer.MAX_VALUE))
            System.out.println("\nThe tree is BST....");
        else
            System.out.println("\nThe tree is not BST....");
    }
}