Is a Binary tree BST but with duplicates are allowed only in right child

Question

I am trying to solve a problem to see if a binary tree is a BST or not. The solution I found is for binary trees with out duplicates. Geeksforgeeks link

int isBST(struct node* node) 
{ 
  return(isBSTUtil(node, INT_MIN, INT_MAX)); 
} 

/* Returns true if the given tree is a BST and its 
   values are >= min and <= max. */
int isBSTUtil(struct node* node, int min, int max) 
{ 
  /* an empty tree is BST */
  if (node==NULL) 
     return 1;

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

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

For duplicates what I did was I just changed the following part. Also duplicates can only be found in the right child i.e all the children in the left child should be smaller the present node but the right child may have the same value as the parent node.

  if (node->data < min || node->data >= max) 
     return 0;
return(isBSTUtil(node->left, min, node->data) && 
isBSTUtil(node->right, node->data, max));

I dont know where I was wrong but some tests are failing. It is an online assessment and I cannot get the test cases where it is failing. Can some one assist me on this.

Have you forgotten the return in the last statement isBSTUtil(node->left, min, node->data) && isBSTUtil(node->right, node->data, max); ? — Papipone, Mar 21 '17 at 03:05
Sorry, it is an edit. I missed it. Editing the question. Thanks for pointing out though — Random, Mar 21 '17 at 03:34
It'll fail on a tree with a single node whose `data` is `INT_MAX`. — Igor Tandetnik, Mar 21 '17 at 03:53

score 1 · Accepted Answer · edited May 23 '17 at 12:00

1

Try the following code:

int isBST(struct node* node) 
{ 
  return(isBSTUtil(node, INT_MIN, INT_MAX)); 
} 

/* Returns true if the given tree is a BST and its 
   values are >= min and <= max. */
int isBSTUtil(struct node* node, long long min, long long max) 
{ 
  /* an empty tree is BST */
  if (node==NULL) 
     return 1;

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

  /* otherwise check the subtrees recursively, 
   tightening the min or max constraint */
  return
    isBSTUtil(node->left, min, long long (node->data) - 1) &&  /*left smaller*/
    isBSTUtil(node->right, node->data, max);  /*right can equal or greater*/
}

To avoid underflow, you should use long long instead of int. long is also 4bytes on some platform and not enough. Thanks for @Bernard for pointing out.

edited May 23 '17 at 12:00

Community

1
1

answered Mar 21 '17 at 06:31

Thomas

130
15

Which modern C++ compiler has different sizes for `long` and `int`? Every modern compiler I know (including GCC, Clang, MSVC, and ICC) treats both of them as 4 bytes whether you are compiling for 32 or 64 bits. – Bernard Mar 21 '17 at 06:38
gcc version 5.4.0 on x64 platform , long is 8 is bytes and int is 4 bytes. Thanks for pointing out. You are right, some platform long and int have the same size. – Thomas Mar 21 '17 at 06:44
Oh, I didn't realize GCC does that. Maybe the OP should be using `long long` then. – Bernard Mar 21 '17 at 06:49
Apparently, GCC only does so on Linux: http://stackoverflow.com/questions/12794603/making-long-4-bytes-in-gcc-on-a-64-bit-linux-machine – Bernard Mar 21 '17 at 06:51
For ref about long and int. So long long is the best practice. http://en.cppreference.com/w/cpp/language/types – Thomas Mar 21 '17 at 06:58
What sort of magic is this :P. I have actually submitted the same solution with out long long and it failed. Now with long long the test case has passed. Can you please give me an example where integeroverflows happens. I greatly appreciate your help @Jett and also Bernard – Random Mar 21 '17 at 13:32
For example, BST has only one node and it's value is INT_MIN, without long long, (node->data - 1) will underflow and cause wrong result. – Thomas Mar 22 '17 at 01:08

Is a Binary tree BST but with duplicates are allowed only in right child

1 Answers1