Test if tree is Binary Search tree

Question

I know i am not supposed to ask these types of question here, but I am stucked and cannot figure out the problem. So, I wrote this code which takes root of the tree as input and check if the given tree is BST or not. But i am failing few test cases and i don't understand why ? If someone can tell me what's wrong in my code that would be very much appreciated. This is the link to question Is This a Binary Search Tree?

Here is the code.

bool checkBST(Node* root) {
    if(root == NULL)
        return false;


        int d = root->data;
        bool r1 = true,r2=true;
        if(root->left != NULL){
            if(d < root->left->data)
                r1 = false;
            else
                r1 = checkBST(root->left);

        }

        if(root->right != NULL){
            if(d > root->right->data)
                r2 = false;
            else
                r2 = checkBST(root->right);
        }
        return r1 && r2;

    }

Are the test cases yours or have you tried writing any test cases yourself? Have you stepped through it with a debugger for interesting test cases? — Max Langhof, Aug 07 '18 at 16:40
Also, please use AND (`&&`) instead of multiplying booleans... — Max Langhof, Aug 07 '18 at 16:42
Also `r1 = false;` on the right side check should probably be `r2 = false;`. — Sani Huttunen, Aug 07 '18 at 16:45

agillgilla · Answer 1 · 2018-08-07T17:01:59.503

1

Why not something like this:

int checkBST(Node *root, int min, int max) {
  /* an empty tree is BST */
  if (root == NULL)
    return true;

  /* false if this node violates the min/max constraint */
  if (root->data < min || root->data > max)
    return 0;

  /* otherwise check the subtrees recursively, 
   tightening the min or max constraint */
  return
  checkBST(root->left, min, root->data - 1) && // Allow only distinct values
    checkBST(root->right, root->data + 1, max);
}

int checkBST(Node *root) {
    return checkBST(root, INT_MIN, INT_MAX);
}

Then you would call the function like this:

checkBST(tree)

Your main problem was that you weren't keeping track of the min and max values that the sub-BST's are restricted by. Also, a null tree is a BST.

edited Aug 07 '18 at 17:01

answered Aug 07 '18 at 16:43

agillgilla

859
1
7
22

Interesting approach. It will work for any numeric data with defined platform limits. it needs a front-end to keep the OPs entry interface. Something tells me the programming challenge site this is pulled from will need that. – WhozCraig Aug 07 '18 at 16:53
@WhozCraig What do you mean "it needs a front-end to keep the OPs entry interface"? – agillgilla Aug 07 '18 at 16:57
The OPs function takes a single node pointer. Yours should as well; at least the initial entry. It is C++, so a simple overload would solve that problem I.e. : `checkBST(tree)` invokes your `checkBST(tree, INT_MIN, INT_MAX)` Otherwise it won't match the expected interface of the testing suite the site expects. – WhozCraig Aug 07 '18 at 17:00
@WhozCraig Oh thanks for the tip. See my edit. – agillgilla Aug 07 '18 at 17:02
Already did, and already ticked. Thanks. – WhozCraig Aug 07 '18 at 17:02

Martin York · Accepted Answer · 2018-08-07T17:12:58.753

1

The problem is probably that you are checking each node against its parent only. Remember the whole sub-tree has to be either side of the parent.

EG

This would pass your code. Each child is the correct value in relation to its direct parent. But 12 is larger than the root 10 but is in the left sub-tree.

#include <climits>

bool checkBST(Node* root, int min, int max) {
    if (!root) {return true;}

    return (min <= root->data && root->data <= max)
        && checkBST(root->left, min, root->data-1)
        && checkBST(root->right, root->data+1, max);
}
bool checkBST(Node* root) {
    return checkBST(root, INT_MIN, INT_MAX);
}

edited Aug 07 '18 at 17:12

answered Aug 07 '18 at 16:58

Martin York

257,169
86
333
562

what are the initial values of INT_MIN and INT_MAX ? – happy sharma Aug 07 '18 at 18:13
@happysharma: They are platform specific min and max value for an int. See: http://www.cplusplus.com/reference/climits/ – Martin York Aug 07 '18 at 19:19
Okay, just one more thing, if you don't mind, i am not able to understand the logic behind passing root->data-1 and root->data+1. Sorry i just started learning Algo and DS. – happy sharma Aug 08 '18 at 10:32
@happysharma So when you search the left sub tree you have to update the max value so it is lower than the current value. So when I call `checkBST(root->left,...)` I set the maximum value to one less than the value of the current node. `root->data-1` – Martin York Aug 08 '18 at 19:06
@happysharma So when you search the right sub tree you have to update the min value so it is larger than the current value. So when I call `checkBST(root->right,...)` I set the minimum value to one more than the value of the current node. `root->data+1` – Martin York Aug 08 '18 at 19:07
I get the solution now. would it be correct if check each node against its parent as well as root node, like i would just pass root->data as max for left tree and min for right tree and not doing root->data-1 or root->data+1 ? – happy sharma Aug 09 '18 at 08:39
@happysharma: No. The point is not to compare it to any nodes above. But to correctly specify the valid range a set of nodes belogs to. – Martin York Aug 09 '18 at 17:27

Test if tree is Binary Search tree

2 Answers2