Check whether a Binary Tree is a Binary Search Tree with BST Definition
Binary Search Tree is Binary Tree and have following properties
0. null is Binary Search Tree
1. Left subtree is BST
2. Right subtree is BST
3. Maximum of left subtree is less than the root node
4. Minimum of right subtree is greater than the root node
            //
// precondition node != null
public static int max(Node node) {
if(node.right != null)
return max(node.right);
else
return node.data;
}

// precondition node != null
public static int min(Node node) {
if(node.left != null)
return min(node.left);
else
return node.data;
}

// BST definition
// 1) left subtree is BST
// 2) right subtree is BST
// 3) max(left substree) < parent.data && min(right subtree) > parent.data
public static boolean isBSTDef(Node node) {
if(node == null)
return true;
else {
if(!isBSTDef(node.left))
return false;

if((node.left != null && max(node.left) >= node.data))
return false;
if(node.right != null && node.data >= min(node.right))
return false;

if(!isBSTDef(node.right))
return false;

return true;
}
}

Use Backtrack to store the previous node
0. Null is Binary Search Tree
1. Use inorder traveral to compare previous and current node
2. Return false if previous node is greater than the current node
            public static boolean isBST(Node root, Node prev) {
if( root != null) {
if(!isBST(root.left, prev))
return false;
if(prev != null && prev.data >= root.data)
return false;
if(!isBST(root.right, root))
return false;
}
return true;
}

Use static variable to store the previous node
0. Null is Binary Search Tree
1. Use inorder traveral to compare previous and current node
2. Return false if previous node is greater than the current node
            public static Node prev = null;
public static boolean isBST(Node r) {
if(r != null) {
if(!isBST(r.left))
return false;
if(prev != null && prev.data >= r.data)
return false;
prev = r;
if(!isBST(r.right))
return false;
}
return true;
}

Generic Version isBST
0. null is BST
1. Left subtree is BST
2. Right subtree is BST
3. Max value of left subtree is less than the parent
4. Min value of right subtree is greater than the parent
            /*
We use something called BiFunction in Java
BiFunction f = (a, b) -> a < b;
f.apply(a, b)

Also there is something called Function
Function f = x -> x + 1;
f.apply(3)

How can I pass three parameters to a function?
There is no TriFunction in Java, but there is way to do it..

f = \x -> x + 1
f = \x y -> x < y
f = \x y z -> x + y + z

*/

class MyNode{
MyNode left;
MyNode right;
T data;
public MyNode(T data){
this.data = data;
}
}

public static  void insert(MyNode r, T t, BiFunction f){
if(r == null){
r = new MyNode(t);
}else{
if(f.apply(t, r.data)){
if(r.left == null)
r.left = new MyNode(t);
else
insert(r.left, t, f);
}else{
if(r.right == null)
r.right = new MyNode(t);
else
insert(r.right, t, f);
}
}
}

public static  MyNode leftSub(MyNode r){
if (r.right != null){
return leftSub(r.right);
}else{
return r;
}
}
public static  MyNode rightSub(MyNode r){
if(r.left != null){
return rightSub(r.left);
}else{
return r;
}
}

/*
1. null is BST
2. left subtree is BST
3. right subtree is BST
4. max(left substree) < parent.data
5. min(right subtree) > parent.data
*/
public static  Boolean isBST(MyNode r, BiFunction f){
if (r != null){
if (!isBST(r.left, f))
return false;

if (r.left != null){
MyNode lmax = leftSub(r.left);
if(!f.apply(lmax.data, r.data))
return false;
}
if (r.right != null){
MyNode rmin = rightSub(r.right);
if(!f.apply(r.data, rmin.data))
return false;
}

if (!isBST(r.right, f))
return false;
}
return true;
}

MyNode r = new MyNode(1);
BiFunction f = (x, y) -> x < y;
insert(r, 3, f);
insert(r, 2, f);
insert(r, 5, f);
inorder(r);

Print.p(isBST(r, f));