Check if binary tree is Binary Search Tree (BST) or not?

Find if binary tree is binary search tree or not.

This is one of the most asked programming interview question.How to check or validate that a given binary tree is a binary search tree (BST)?

Binary search tree property
All the nodes on the left side of a given node are smaller and all on the right side are greater than the given node. So, essentially, any tree is a binary search tree if both its left sub tree and right sub tree are BST and root satisfy above condition.
Binary tree is Binary Search Tree (BST) if
1. Left sub tree is BST
2. Right sub tree is BST
3. Value of root is greater than max in left sub tree and less than minimum in right sub tree
Following figure explains which is binary search tree and which is not.

Check if tree is binary search tree


No further analysis is required for this problem.

Notes :
I have gone through codes which are simpler but are based on assumption regarding the range of data in tree. This code is generic and does not make any assume anything about data in tree.
Some implementations do the check for root first and then go forward to check it for left and right sub tree. In that case, they could not use the information that both left and right sub tree are Binary Search Tree while finding max and minimum in those trees. Above implementation uses that information.

Watch video here


Implementation of find_maximum and find_minimum can be found in this post

Code of checking if binary tree is binary search tree

Above code is correct but inefficient because for every node check, its left and right sub tree needs to be traversed and max and min needs to be found. It make algorithm complexity of O(n2).
There is another method where we use the same min and max concept, however keeping track of the max which needs to be there on left side and minimum on the right side. Start from INT_MAX and INT_MIN, check if the root node is greater than max and less than the min. If yes, than go down left subtree with max changed to root value, and go down to right subtree with min changed to root value. By doing so, we are applying the same method as above that minimum node in right side should be greater than root and maximum in the left side should be less than root value.Code below implements this method

Complexity of above implementation is O(n) as we are traversing each node only once.
There is another method to find if binary tree is binary search tree or not. That is to do inorder traversal of binary tree and keep track of previous node. As we know inorder traversal of a binary search tree gives us elements in sorted order, previously visited node should be always smaller than the current node. If all nodes satisfy this property, binary tree is binary search tree. And as soon as this property is violated at any node, we can say tree is not a binary search tree. 
Complexity of this implementation is also O(n) as we will be traversing each node only once. Code snippet for above method:

Test cases

1. A BST as an input
2. A non BST as an input
3. A null tree
4. A tree where left sub tree of root is BST but max in left tree is greater than root.
5. Same as 4 where minimum in right sub tree is less than root.

3 thoughts on “Check if binary tree is Binary Search Tree (BST) or not?”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s