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
No further analysis is required for this problem.
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
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:
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.