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

Problem is given a binary tree, find if tree is binary search tree or not? 

As per definition of binary search tree, a binary tree is called as binary search tree if for each node, all nodes on left are smaller and on right are greater than current node.

For example, binary tree given below is a BST,

LCA

Whereas this one is not.

If tree is BST or not

Essentially, any tree is a binary search tree if both its left sub tree and right sub tree are BST and root satisfies binary tree definition.

Binary tree is Binary Search Tree if : Left subtree is BST ; Right subtree is BST and value of root is greater than max in left subtree and less than minimum in right subtree

Above conditions tells us that there is recursion involved as result of subtree decide result of whole tree. Question is what should be termination condition and what should each call of function return?

Each function call should return if there tree passed to it is a BST or not. At root, find max of left subtree and min of right subtree and then check for binary search tree condition.

Following figure explains which is binary search tree and which is not.

Check if tree is binary search tree

Notes :
I have gone through codes which are simpler but are based on assumption about range of data in tree. This code is generic and does not assume anything about data in tree.

Some implementations do 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.

Implementation to find if binary tree is binary search tree

Above code is correct but inefficient because for each 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 same min and max concept is used, however keeping track of max which needs to be there on left side and minimum on the right side. Start from min as INT_MAX and max as INT_MIN, check if current node is greater than max and less than 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. 


Complexity of implementation is O(n) as each node is traversed 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 inorder traversal of a binary search tree gives elements in sorted order, previously visited node should be always smaller than current. If all nodes satisfy this property, binary tree is binary search tree. And if this condition is violated at any node, tree is not a binary search tree.

Complexity of this implementation is also O(n) as we will be traversing each node only once.

Please share if there is something is wrong or missing. We would love to hear what you have to say. Sharing is caring.

  • http://www.blogger.com/profile/13245587252896669334 MPG

    Nice one, clean & clear to understand.

    • http://www.blogger.com/profile/07885594236543253450 Jitendra Sangar

      Thanks!

    • http://www.blogger.com/profile/07885594236543253450 Jitendra Sangar

      Thanks!

  • Kunal singh

    Sir can you comment on the complexity of this program.I think it is O(n^2).as you are visiting each node more than once.

    • http://algorithmsandme.in/ Jitendra Sangar

      That makes sense. However, we can store the max and min calculated once and use it, so that we do not scan the two sub trees again and again.
      Good catch, will update the post. Thanks

      • Kunal singh

        Or sir we can use inorder traversal.As inorder traversal gives the output in ascending order,All we need to check is weather the current node is larger than the last .I hope that would do.