Is given binary tree is binary search tree or not

Question

I have written a function that returns true if given binary tree is binary search tree else returns false.

bool IsBst(node* root)
{
    if(root->left == NULL && root->right == NULL)
    {
        return true;
    }
    if(root->left->data <= root->data && root->right->data > root->data)
    {
        return (IsBst(root->left) && IsBst(root->right))
    }
    else
    {
        else false;
    }
}

Is my function right?

Will this function return right answer?

I have doubt in case of if left child is null then what will this comparison root->left->data<=root->data return?(If there is NULL)

Help me to improve this! Thanks in advance!

Answer 1

It should be something like

bool IsBst(const node* root, node* minNode = nullptr, node* maxNode = nullptr)
{
    if (root == nullptr) {
        return true;
    }
    if (minNode != nullptr && root->data < minNode->data)
    {
        return false;
    }
    if (maxNode != nullptr && maxNode->data < root->data)
    {
        return false;
    }
    return IsBst(root->left, minNode, root)
        && IsBst(root->right, root, maxNode);
}

Answer 2

If you're using C++ 17 and above, you can do it even more elegantly by using an optional class. Hence, you don't need to do nullptr checks for min and max:

bool checkBST0(const Node* root, const std::optional<int>& min, const std::optional<int>& max) {
    if (root != nullptr) {
        const auto data = root->data;
        if ((min.has_value() && min <= data) || 
            (max.has_value() && max >= data)) {
            return false;
        }
            
        std::optional<int> opt(data);
        return checkBST0(root->left, opt, max) && checkBST0(root->right, min, opt);
    }
        
    return true;
} 

Initially, you should call this method with an optional without any value:

std::optional<int> emptyOptional;
return checkBST0(root, emptyOptional, emptyOptional);  

Answer 3

Nope, it's not right. It would fail on this tree:

     3
      \
       \
        5