Check if a given tree is Binary Search Tree or not

Introduction

How do we know that a given binary tree is a binary search tree?

Definition of BST:

All the nodes on the left side of a given node are smaller and all nodes 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 binary search tree and root satisfy the binary search tree condition.

So, tree is binary search tree if

1. Left sub tree is binary search tree

2. Right sub tree is binary search tree

3. Value of root is greater than max in left sub tree and less than minimum in right sub 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 BST while finding max and minimum in those trees. Above implementation handles uses that information.

Implementation of find_maximum and find_minimum can be found in this post

Code

int isBST(Node * node){

  if(!node)

       return 1;

  int is_left  = isBST(node->left);

  int is_right  = isBST(node->right);

  if(is_left && is_right){

  /* Since we already know that left sub tree and

 right sub tree are Binary search tree, finding min and max in them would be easy */

   

   Node *max   = find_maximum(node->left);

   Node *min   = find_minimum(node->right);

   //case 1 : Leaf node

    if(!max && !min)

        return 1;

   //Case 2 : only left sub tree is there

    if(max && !min)

        return node->value > max->value;

   //Case 3 : Only right sub tree is there

    if(!max && min)

       return node->value < min->value;

   //Case 4 : Both left and right sub tree are there

    if(node->value > max->value && node->value < min->value)

       return 1;

   }

   return 0;

}

Test cases 

1. A binary search tree as an input

2. A non binary search tree 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.