CODEWITHSUNDEEP
c++data-structurestreebinary-treebinary-search-tree
mistletoe
mistletoe

Reputation: 493

Function to check whether a binary tree is binary search tree or not working

Can someone tell me why is this not working? This seems correct to me

please someone look into this.

I am not able to find my mistake.

bool checkbst(node* root,int minValue,int maxValue)
{
   if(root==NULL)
   {

       return true;
   }
   else if(((root->data)>(minValue))&&
           ((root->data)>(maxValue))&&
           (checkbst(root->left,minValue,root->data))&&
           (checkbst(root->right,root->data,maxValue)))
   {

       return true;
   }
   else
   {

     return false;
   }
}

void isbst(node* root)
{
   if( checkbst(root,INT_MIN,INT_MAX))
   {
       cout<<"the tree is bst";
   }
}

Upvotes: 0

Views: 1322

Answers (4)

MadangLighthouse
MadangLighthouse

Reputation: 11

Here is a solution that is O(n) time complexity and O(1) space. It uses in-order tree traversal to confirm that the tree is sorted according to BST rules, but it does not rely on maintaining an auxiliary array of in-order traversed Nodes. However, because it does rely on recursion it's usage of the stack (i.e. stack depth) can reach O(logn).

struct Node
{
    int data;
    struct Node* left;
    struct Node* right;
};

bool isBSTHelper(Node* root, int& min, int& max)
{
    if (nullptr == root)
    {
        max = numeric_limits<int>::min(); // has meaning for LHS traversal.
        min = numeric_limits<int>::max(); // has meaning for RHS traversal.
        return true;
    }

    int lhsMax;
    int lhsMin;
    if (!isBSTHelper(root->left, lhsMin, lhsMax) ||
        lhsMax >= root->data)
    {
        return false;
    }

    int rhsMax;
    int rhsMin;
    if (!isBSTHelper(root->right, rhsMin, rhsMax) ||
        rhsMin <= root->data)
    {
        return false;
    }

    min = std::min(lhsMin, root->data);
    max = std::max(rhsMax, root->data);

    return true;
}

bool isBST(Node* root)
{
    int min;
    int max;
    return isBSTHelper(root, min, max);
}

Upvotes: 0

Anagh Hegde
Anagh Hegde

Reputation: 335

I have checked your there is a small mistake code but there is a better way to do it. You just have to do the in order traversal of the given tree and store it in a array and then check if the elements in the array are sorted. If the elements are sorted then its a binary search tree else it will be a binary tree (which is a kind of basic difference between a binary tree and binary search tree).

There is a small mistake in your code 

((root->data)>(maxValue))

should be

((root->data)<(maxValue))

Upvotes: 0

lrleon
lrleon

Reputation: 2648

Your code verifies that the keys are inside a range, but it does not verify if the children satisfy the bst condition respect to the root. That is, the keys in the left subtree must be lesser than the root and the keys in the right one greater. You should check if the children are not null before doing any comparison involving subtrees.

This version should work:

bool checkbst(node* root, int minValue,int maxValue)
{
  if (root == nullptr) 
    return true;

  if (not (root->data >= minValue && root->data <= maxvalue))
    return false;

  if (root->left)
    {
      if (root->data < root->left->data)
        if (not checkbst(root->left, minValue, maxValue))
          return false;
      else 
        return false;
    }

  // here the left subtree has been checked
  if (root->right)
    {
      if (root->data < root->right->data)
        return checkbst(root->right, minValue, maxValue);
      else
        return false;
    }

  return true; // everything is ok
}

Upvotes: 0

helgaker
helgaker

Reputation: 21

You have a typo in checkbst, you are checking

((root->data)>(minValue))&&((root->data)>(maxValue))

while it probably should be 

((root->data)>(minValue))&&((root->data)<(maxValue))

(notice the "less than" sign).

Upvotes: 2

Related Questions