Monday, January 16, 2012

A program to check if a binary tree is Binary Search Tree

The basic theory behind this implementation is that the inorder traversal of binary search tree(BST) gives elements in sorted order. So if we traverse the tree and each time we visit next element we get some higher value then we can conclude that the give binary tree is a BST.

bool isBst(node* r)
{
static int no = INT_MAX +1;

if(r == NULL)
return true;
else
{
if(!isBst(r ->left))
return false;
if(r->data > no)
no = r->data;
else
return false;
if(!isBst(r ->right))
return false;
}
return true;
}

No comments: