Check if a Binary tree is a BST or Not?

Hello everyone,

This post will cover the easy and simple solution for checking if the given binary tree is a binary search tree (BST) or not.

Check for BST | Practice | GeeksforGeeks

Before getting directly into the algorithm, let’s take an example

Suppose the given tree is :

Binary Search Tree — YES

In order traversal of the binary tree given of left side is given an array = {0, 2, 3, 4, 5, 6, 7, 8, 9}.

Now as we can see the array is SORTED since the given binary tree is BST.

Now let’s see the inorder traversal of the binary tree which is NOT a BST.

Binary Search Tree — NO

In order traversal of the binary tree given of left side is given as array = {2, 17, 7, 19, 3, 100, 25, 36, 1}.

Now you can see the array is NOT SORTED since the given binary tree is not a BST.

Now let's get into the algorithm for the same.

Algorithm

1. First we will be doing InOrder traversal and store the data in a simple ArrayList (in java).
2. Now check if the arrayList of the data we have found is sorted or not.
3. If sorted then output true (means the given binary tree is BST).
4. Else output false.

You can check out the complete code here.

Hope you have liked the post and if you have any suggestion then please let me know in comments.

Cheers!!