# Check whether a given tree is a Binary Search Tree in Java

In this Java tutorial, we will solve a well-known problem of Tree data structure. Given a tree, we will check whether the given tree is a Binary search tree or not.

## Binary Search Tree in Java

A binary tree is a tree which has at most two children of a node. A binary search tree is a binary tree with some special properties:

• The node value must be greater than all the node values in the left subtree.
• The node value must be less than all the node values in the right subtree.
• Both left and right subtrees must also be a binary search tree.

### Algorithm of Binary search tree

We will make a recursive function and we call this function for the root node.

For solving this problem we will use the following steps:

1. Call the function for the left node.
2. Call the function for the right node.
3. If the left subtree is not a BST then the tree is not a BST.
4. If the right subtree is not a BST then the tree is not a BST.
5. And, If node value is less then the max value of the left subtree then the tree is not a BST.
6. Also, If the node value is greater than the minimum value of the right subtree the tree is not a BST.
7. Else, the tree is a BST.

## Program to check whether a given tree is Binary Search Tree in Java

```public class BST {
public static void main(String[] args) {
/* Tree:
50
/  \
10   20
/  \   /  \
30   60  70  80

*/
TreeNode root = new TreeNode(50);
root.left = new TreeNode(10);
root.right = new TreeNode(20);
root.left.left = new TreeNode(30);
root.left.right = new TreeNode(60);
root.right.left = new TreeNode(70);
root.right.right = new TreeNode(80);

System.out.println(isBST(root).isBst);

/* Tree:
50
/  \
20   70
/  \   /  \
10   30 60  80

*/
TreeNode root2 = new TreeNode(50);
root2.left = new TreeNode(20);
root2.right = new TreeNode(70);
root2.left.left = new TreeNode(10);
root2.left.right = new TreeNode(30);
root2.right.left = new TreeNode(60);
root2.right.right = new TreeNode(80);

System.out.println(isBST(root2).isBst);

}

static class TreeNode {
int val;
TreeNode left;
TreeNode right;

TreeNode(int x) {
val = x;
left = null;
right = null;
}
}

static class BSTtriplet {
boolean isBst;
int max;
int min;
}

static BSTtriplet isBST(TreeNode root) {
if (root == null) {
BSTtriplet br = new BSTtriplet();
br.isBst = true;
br.max = Integer.MIN_VALUE;
br.min = Integer.MAX_VALUE;
return br;
}

BSTtriplet lr = isBST(root.left);
BSTtriplet rr = isBST(root.right);

BSTtriplet myRes = new BSTtriplet();
if (!lr.isBst || !rr.isBst || root.val < lr.max || root.val > rr.min) {
myRes.isBst = false;
} else {
myRes.isBst = true;
}

myRes.min = Math.min(root.val, Math.min(lr.min, rr.min));
myRes.max = Math.max(root.val, Math.max(lr.max, rr.max));
return myRes;
}
}
```

Output:

```false
true```