RTE in the bst program

Question

I have to check if this is BST or not i have implemented recursion and it is giving run time error for the tree level order 2 N 7 N 6 N 5 N 9 N 2 N 6

bool isBST(Node* root) 
    {
        if(root==NULL)
            return 1;
        if(root->left==NULL && root->right==NULL)
            return 1;
        if((root->data)<(root->left->data))
            return 0;
        if( (root->data)>(root->right->data))
            return 0;
        if(root->right==NULL)
            return isBST(root->left);
        if(root->left==NULL)
            return isBST(root->right);
        if(!isBST(root->left) || !isBST(root->right))
        {
            return 0;
            }
        return 1;
    }

Answer 1

Your code may dereference a null pointer. For instance, if root has a right child, but not a left child, then this code will be executed which performs an invalid dereference:

if((root->data)<(root->left->data))

But even if you add the necessary checks to avoid such invalid dereferencing, the algorithm is not correct.

It is not true that the following conditions define a valid BST:

• The left child of a node is either null or has a value that is not greater than the node's own value, AND
• The right child of a node is either null or has a value that is not less than the node's own value, AND
• The above is also true for the left and right child (recursive step)

For instance, this would all be true for this tree:

         5
        / \
       2   8
        \
         7

... but this tree is not a valid BST, because 7 is greater than 5, which is not allowed. All values in the left subtree of a node must not be greater than the node's own value. Your code only checks this for the direct child, but it should make sure that this is also true for any other descendants in that left subtree.

The common way to make a correct verification, is to pass to the recursive call a window (minimum and maximum) of values which the subtree may contain.