Simple C Program to check whether the given Binary Tree is Binary Search Tree or not

This can be done in many ways . The simplest way is by using the Inorder Traversal . If we traverse a binary search tree using inorder traversal all the elements are in sorted order .

For the above binary search tree Inorder traversal is

 1  2  3  4  5  6  7

In the following code flag is used like a boolean varible . In the Inorder traversal if the elements are not in sorted order flag is set to 0 . The variable 'min' is used to store the previous value in inorder traversal . Initially it is assigned to the mininum integer value possible which is -32768.

Code :(in C)

	void CheckBST(struct node* root)
	{
	int flag=1,min=-32768;
	if(root==null)
	{
	printf("Empty Tree");
	return;
	}
	IsBst(root,&min,&flag);
	if(flag==1)
	printf("Binary Search Tree");
	else
	printf("Not a Binary Search Tree");
	}
	void IsBst(struct node* node,int *min,int *flag)
	{
	if(node!=null)
	{
	IsBst(node->left,min,flag);
	if(node->data < *min)
	{
	*flag=0;
	return;
	}
	else
	*min=node->data;
	IsBst(node->right,min,flag);
	}
	}

view raw isbst.c hosted with ❤ by GitHub

Please let me know if you have any questions .