C-program to check whether a binary tree is a Binary search tree

8. Write a C program to check if a given binary tree is a binary search tree or not?
Solution:
If the given binary tree is a Binary search tree,then the inorder traversal should output the elements in increasing order.We make use of this property of inorder traversal to check whether the given binary tree is a BST or not.We make note of the latest element that could have been printed and compare it with the current element.Given below is a C function to check it.

bool flag=true;
void inorder(tree T,int *lastprinted)
{
if(T==NULL)
  {
   printf("the tree is empty .Hence, it is a BST\n");
  }
else
{
  if(T->left!=NULL)
  {
      inorder(T->left,lastprinted);
  }
  if(T->data > *lastprinted)
  {
     *lastprinted=T->data;
  }
  else
  {
     printf("the given binary tree is not a BST\n");
     flag=false;
     exit(0);
  }
  inorder(T->right,lastprinted);
  }
}

Now check the value of flag to say whether it is a BST or not.If it is not then it is already taken care by the code.

Click Here For More Questions