3

Is this method wrong for finding out if the tree is a BST or not? The left subtree of a node contains only nodes with keys less than the node’s key.The right subtree of a node contains only nodes with keys greater than the node’s key.And Both the left and right subtrees must also be binary search trees. My code is:

isBST(struct node* node) 
{ 
  if (node == NULL) 
    return 1; 
  if (node->left != NULL && node->left->data > node->data) 
    return 0; 
  if (node->right != NULL && node->right->data < node->data) 
    return 0; 
  if (!isBST(node->left) || !isBST(node->right)) 
    return 0; 
  return 1; 
}
Yu Hao
  • 119,891
  • 44
  • 235
  • 294
user2227862
  • 595
  • 3
  • 9
  • 16
  • 2
    Though your code is not correct (see the answers), you also need to remember to include equality in one of your checks (either >= or <=), (depending where you wish equal nodes to be). – Bernhard Barker Jul 05 '13 at 14:44
  • possible duplicate of [How do you validate a binary search tree?](http://stackoverflow.com/questions/499995/how-do-you-validate-a-binary-search-tree) – Bernhard Barker Jun 17 '14 at 12:09

1 Answers1

10

No this method is wrong because it would return a true answer for this tree:

     6
    / \
   4   9
  / \
 2   10

Although it is not a binary search tree! I would suggest a better approach would be to take the inorder traversal and verify if it is actually sorted.

poorvank
  • 7,524
  • 19
  • 60
  • 102