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 is

Method 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.

Thanks to Dhaval for suggesting this approach and Article

#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 at : 
http://ideone.com/e.js/HDWFLL
http://ideone.com/e.js/3h1Q25
Labels: , , , ,