Search code examples
c++recursionbinary-search-treenodes

Issue with function to check if tree is a BST

So I have a function to check if a tree is a bst(if every node only has smaller values on its left and larger values on its right). Every other function works and the problem is with this one (second one just calls helper). I think the issue has something to do with the recursive call root-left hitting null but I am not sure and even if it is not sure how to fix. Can add more code as needed. Any help is appreciated.

visual studio error i get is : R00t -> left was nullptr other compiler: segmentation fault core dumped. 

bool isBSThelper(TreeNode* R00t) 
{



        if (R00t == NULL)
            return true;
        //if (R00t->left != NULL && (R00t->info < R00t->left->info))
        if (R00t->info < R00t->left->info)
            return false;
        //if (R00t->right != NULL && (R00t->info < R00t->right->info))
        if (R00t->info > R00t->right->info)
            return false;

        return isBSThelper(R00t->left) && isBSThelper(R00t->right);



}

bool TreeType::isBST() const
{
    return isBSThelper(root);
}
Solution

  • According to your comment

    even with if (R00t->left != NULL || R00t->right != NULL) error persists

    the problem would persist. Let me rewrite and iterate from there (since I can't comment to ask for clarification -new user). If your code was like

    bool isBSThelper(TreeNode* R00t) {
    if ( R00t == NULL )
        return true;
    if ( R00t->left != NULL || R00t->right != NULL ) {
        if ( R00t->info < R00t->left->info )
            return false;
        if ( R00t->info < R00t->right->info )
            return false;
    }

    return isBSThelper(R00t->left) && isBSThelper(R00t->right);
}

    then you would potentially still encounter the same problem, since the expression

    if (R00t->left != NULL || R00t->right != NULL) {

    would still make this expression with values

    R00t->left != NULL

    but

    R00t->right == NULL

    evaluate to true.

    One solution might be

    1. To make sure R00T->left and R00t->right are either valid (pointing to a node) or NULL (preferably nullptr if you are using C++)
    2. And code like this:
    bool isBSThelper( TreeNode* R00t ) {
    if ( R00t == NULL )
        return true;
    if ( R00t->left != NULL && R00t->info > R00t->left->info )
        return false;
    if ( R00t->right!= NULL && R00t->info > R00t->right->info )
        return false;

    return isBSThelper( R00t->left ) && isBSThelper( R00t->right );
}

    And the problem would be no more. (1) is critical.

    An additional note: Your code does not check

    if (R00t->left != NULL && R00t->right!= NULL && R00t->left->info < R00t->right->info)
        return false;

    which is another property of a Binary Search Tree (or obviously using ">" instead of "<" here as you see fit).