C Program to determine whether the given tree is Binary Search Tree or not?

Question

I am writing the below code in C Programming language to determine whether a given tree is binary search tree or not. But I am getting a segmentation error. Can anyone help me in understanding what I am doing wrong here?

struct node {
    int val;
    struct node *left;
    struct node *right;
};

int isBST(struct node* root) {
    if(root == NULL) {
        return 1;
    }
    if(root->left->val >= root->val || root->right->val <= root->val) {
        return 0;
    }
    return (isBST(root->left) && isBST(root->right));
}

I am trying to check if the value of the left node is lower than the value of the current node and value of the right node is greater than the value of the current node. Also using recursion, I am repeating this process for the left and right subtrees. I was expecting a true or false but got the segmentation error.

Answer 1

A binary search tree is a binary tree where the value of each node is larger than all values in the left subtree and smaller than all values in the right subtree.

The OP code has two issues:

• There is no check for the left or right pointers being NULL.
• The condition that the current value is larger than the value of the left child node and smaller than the value of the right child node is a necessary, but not sufficient condition for a binary search tree.

For example, if the root node has value 10 and a left node with value 5 which again has a right node with value 15, then the check of immediate child nodes will pass, but the tree is not a binary search tree.

The idea of the following implementation is to traverse the tree in order as a binary search tree and verify that the nodes are actually in order which is the case if and only if the tree is a binary search tree:

// Helper function for traversal and checking order
int isBSTTraversal(struct node* root, struct node** prev) {
    if(root == NULL) {
        return 1;
    }
    if(!isBSTTraversal(root->left, prev)) {
        return 0;  // Left subtree not BST
    }
    if(*prev != NULL && root->val < (*prev)->val) {
        return 0;  // Visited values are out of order: not a BST
    }
    *prev = root;
    return isBSTTraversal(root->right, prev);
}

int isBST(struct node* root) {
    struct node* prev = NULL;
    return isBSTTraversal(root, &prev);
}