Check Binary Tree is Binary Search Tree or not

To search Binary Search Tree
First lets understand characteristics of BST
• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.
• Each node (item in the tree) has a distinct key.
First Logic Comes in mind isMethod 1) For each node, check if left node of it is smaller than the node and right node of it is greater than the node.
But is wrong.
Take below Example which satisfies condition. but not a BST.

           [3]
          /   \
       [2]     [5]
      /   \    /  \
    [1]  [4] [0]  [8]

Method 2) Simply Print In Order Traversal of Tree and check all are in ascending order or not.
To optimize Storing of inorder traversal , we can check in place.

#include <stdio.h>
#include <stdlib.h>
struct node
{
    int data;
    struct node* left;
    struct node* right;
};
struct node* newNode(int data)
{
  struct node* node = (struct node*)
                       malloc(sizeof(struct node));
  node->data = data;
  node->left = NULL;
  node->right = NULL;

  return(node);
}
int isBST(struct node* root)
{
    static struct node *prev = NULL;
    if (root){
        if (!isBST(root->left))
          return 0;
        if (prev != NULL && root->data <= prev->data)
          return 0;
        prev = root;
        //To keep track of previous node Mark that its STATIC
        return isBST(root->right);
    }
    return 1;
}

int main(void) {
  //BST
  struct node *root = newNode(4);
  root->left        = newNode(2);
  root->right       = newNode(5);
  root->left->left  = newNode(1);
  root->left->right = newNode(3); 
  //Not A BST
  /*struct node *root = newNode(3);
  root->left        = newNode(2);
  root->right       = newNode(6);
  root->left->left  = newNode(1);
  root->left->right = newNode(5);
  */
  if(isBST(root))
    printf("Is BST");
  else
    printf("Not a BST");
  return 0;
}

Visit Full Working Code of Mehtod 2 at : http://ideone.com/e.js/3h1Q25

Now We can think like, If we have order and all nodes in increasing order then we can say its BST, We can think of an approch in which we pass min and max value so far in recursion.
and We can decide weather it is BST or not.

Algorithm would be similar to this

int isBST(struct node* node) 
{ 
  return(isBSTUtil(node, min_so_far, max_so_far)); 
} 

int isBSTUtil(struct node* node, int min_so_far, int max_so_far) 
/* Returns true if the given tree is a BST and its values are >= max_so_far and <= max_so_far. */

Code for above algorithm is

int isBST(struct node* node) 
{ 
  return(isBSTUtil(node, INT_MIN, INT_MAX)); 
} 
 
int isBSTUtil(struct node* node, int min, int max) 
{ 
  if (node==NULL) 
     return 1;
       
  if (node->data < min || node->data > max) 
     return 0; 
 
  return
    isBSTUtil(node->left, min, node->data-1) && isBSTUtil(node->right, node->data+1, max);  
}

As inOrder traversal of BST is in sorted order like 1,2,3,4,5.
I can think of approach in which I can keep just One variable Prev and find weather all nodes are larger than previous one or not.
If this condition fails, Its not BST, example : 1,3,2,4,5,6
initially when node’s data is 1, prev is Int_min, so condition satisfies
When node’s data is 3, prev is 1, so condition satisfies.
When node’s data is 2, prev is 2, so its not satisfying

See Code for above Logic

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
struct node
{
    int data;
    struct node* left;
    struct node* right;
};
struct node* newNode(int data)
{
  struct node* node = (struct node*)
                       malloc(sizeof(struct node));
  node->data = data;
  node->left = NULL;
  node->right = NULL;
 
  return(node);
}
int isBST(struct node* root,int prev)
{
  if (!root) return 1;
  
  if (isBST(root->left, prev)) {
  	
    if (root->data > prev) {
      prev = root->data;
      return isBST(root->right, prev);
    } 
    else return 0;
  }
  else return 0;
}

int main(void) {
  //BST
  struct node *root = newNode(4);
  root->left        = newNode(2);
  root->right       = newNode(5);
  root->left->left  = newNode(1);
  root->left->right = newNode(3); 
  //Not A BST
  /*struct node *root = newNode(3);
  root->left        = newNode(2);
  root->right       = newNode(6);
  root->left->left  = newNode(1);
  root->left->right = newNode(5);
  */
  if(isBST(root,INT_MIN))
    printf("Is BST");
  else
    printf("Not a BST");
  return 0;
}