Valid Binary Search Tree

Question: Write a function to find whether a given binary tree is a binary search tree ?


Find below a recursive algorithm to find whether a given binary search tree is valid or not. This algorithm, starting from the root node, at each node verifies whether current node data lies between min and max possible value for that node and also check if the left and right subtree are valid binary search trees. Since node data in my tree is an integer, thus starting min and max values used are 0x80000000 and 0x7fffffff. However, these values will depend on minimum and maximum possible values of the key. In addition, following algorithm assumes no duplicate keys; if duplicate keys are present, the condition in line 8 and 9 needs to be modified.


Time complexity: O(n)


bool
is_valid_bst_helper(tree *t, int min, int max)
{ 
    if (t == NULL) {
        return TRUE;
    }   
  
    if (t->data > min &&
        t->data < max &&
        is_valid_bst_helper(t->left, min, t->data) &&
        is_valid_bst_helper(t->right, t->data, max)) {
        return TRUE;
    }   

    return FALSE;
}

bool
is_valid_bst(tree *t) 
{
    return(is_valid_bst_helper(t, 0x80000000, 0x7fffffff));
}