Verify a Binary Search Tree or implement isBST().

Solution #1: A Binary Search Tree can be verified using its property that the left child is smaller than the root which is smaller than the right child. But checking just that does not suffice as in the below case, such an approach will fail,

            8
        /        \
     4          16
   /    \       /     \
 2     9    10     20

Approach: Every node's data must lie between a 'min' and a 'max' value. These values are adjusted as we move through the recursion. If we move to the left child, the 'max' value becomes the value of the parent's data as no node in the left tree can have a value greater than the parent. Similarly, as we move to the right child, the 'min' value becomes the value of the parent's data as no node in the right tree can have a value lesser than the parent. Here is the code,

int isBST(struct node* root, int min, int max)
{
    if(root == NULL)
        return 1;

    if((root->data < min) || (root->data > max))
        return 0;

    return isBST(root->left, min, root->data) && isBST(root->right, root->data, max);
}

int main()
{
    struct node *root;

    insert(&root, -10);
    insert(&root, -20);
    insert(&root, 30);
    insert(&root, -5);
    insert(&root, 40);

    printf("isBST = %d\n", isBST(root, INT_MIN, INT_MAX));
    return 0;
}