# Check If A Binary Tree Is Binary Search Tree

## Binary Search Tree

This tutorial will check if a Binary Tree is Binary Search Tree or not. It is known that a binary search tree (BST) is a node based binary tree data structure which satisfies the following properties:

• The left sub-tree of a node contains only nodes with keys less than the root node’s key.
• The right sub-tree of a node contains only nodes with keys greater than the root node’s key.
• Both the left and right sub-trees must also be again binary search trees.

I will implement the algorithm using Java program in `O(n)` time complexity to check whether the Binary Tree is Binary Search Tree or not.

## Prerequisite

Knowledge of Java

## Binary Search Tree Check

The following Java source code will check if a binary tree is binary search tree (BST) or not.

```public class BinaryTree {
Node root;
Node prev;
public static void main(String[] args) {
BinaryTree binaryTree = new BinaryTree();
binaryTree.root = binaryTree.new Node(5);
binaryTree.root.left = binaryTree.new Node(3);
binaryTree.root.right = binaryTree.new Node(6);
binaryTree.root.left.left = binaryTree.new Node(1);
binaryTree.root.left.right = binaryTree.new Node(2);
System.out.println(binaryTree.isBST(binaryTree.root));
}
private boolean isBST(Node node) {
if (node != null) {
if (!isBST(node.left)) {
return false;
}
if (prev != null && node.data <= prev.data) {
return false;
}
prev = node;
return isBST(node.right);
}
return true;
}
private class Node {
int data;
Node left, right;
public Node(int data) {
this.data = data;
this.left = this.right = null;
}
}
}```

In the above class I have used recursive function to check if a binary tree is binary search tree or not.

## Testing Binary Search Tree

Please run the above class, you should see the following output:

`false`

Therefore the above binary tree is not a binary search tree.

Now replace

`binaryTree.root.left.right = binaryTree.new Node(2);`

by

`binaryTree.root.left.right = binaryTree.new Node(4);`

and run the above code again, you should see the following output:

`true`