## Introduction

This tutorial will check if a Binary Tree is Binary Search Tree or not. We know 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.

We 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

## Source Code

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 we have used recursive function to check if a binary tree is binary search tree or not.

## Testing the Application

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`

Thanks for reading.

**Tags:**Search