To find if a tree is a binary search tree or not

Question

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; 
}

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
possible duplicate of How do you validate a binary search tree? — Bernhard Barker

poorvank poorvank · Accepted Answer · 2013-07-05T14:28:18

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

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.

To find if a tree is a binary search tree or not

1 Answers