CODEWITHSUNDEEP
c++c++11treebinary-treebinary-search-tree
Random
Random

Reputation: 979

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

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.

Upvotes: 0

Views: 311

Answers (1)

Thomas
Thomas

Reputation: 130

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.

Upvotes: 1

Related Questions