CODEWITHSUNDEEP
c++algorithmtreebinary-search-tree
Varun Kamani
Varun Kamani

Reputation: 86

Is given binary tree is binary search tree or not

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!

Upvotes: 2

Views: 269

Answers (3)

CiaPan
CiaPan

Reputation: 9570

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

     3
      \
       \
        5

And it would give a wrong answer on this one:

      4
     / \
    /   \
   /     \
  2       6
 / \     / \
1   9   0   8

A BST is defined as a tree, whose each internal node stores a key greater than all the keys in the node’s left subtree and less than those in its right subtree (see the Wikipedia article).

So it's not enough for a 1-2-9 left subtree in my example to have a left node value less than it's root (1<2) and the right node greater than it (9>2). It should also satisfy the condition that all its nodes have values less than 4, the value in the whole tree's root.

Here is an example in C I gave in the answer to the question Pseudo code to check if binary tree is a binary search tree - not sure about the recursion:

// Test a node against its closest left-side and right-side ancestors
boolean isNodeBST(NODE *lt, NODE *node, NODE *rt)
{
    if(node == NULL)
        return true;
    if(lt != NULL && node->key <= lt->key)
        return false;
    if(rt != NULL && node->key >= rt->key)
        return false;

    return
        isNodeBST(lt, node->left, node) &&
        isNodeBST(node, node->right, rt);
}

boolean isTreeBST(TREE *tree)
{
   return isNodeBST( NULL, tree->root, NULL);
}

Upvotes: 0

Anatolii
Anatolii

Reputation: 14660

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, min, opt) && checkBST0(root->right, opt, max);
    }
        
    return true;
}

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

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

Upvotes: 0

Jarod42
Jarod42

Reputation: 217245

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);
}

Upvotes: 0

Related Questions