i have found the following code on net to check if the binary tree is
bst or not
/*
Returns true if a binary tree is a binary search tree.
*/
int isBST(struct node* node) {
if (node==NULL) return(true);
// false if the min of the left is > than us
if (node->left!=NULL && minValue(node->left) > node->data)
return(false);
// false if the max of the right is <= than us
if (node->right!=NULL && maxValue(node->right) <= node->data)
return(false);
// false if, recursively, the left or right is not a BST
if (!isBST(node->left) || !isBST(node->right))
return(false);
// passing all that, it's a BST
return(true);
}
int minValue(struct node* node) {
struct node* current = node;
// loop down to find the leftmost leaf
while (current->left != NULL) {
current = current->left;
}
return(current->data);
}
and maxvalue also similarly returns right most vaslue of tree..
now i have a doubt that here v r comparing the node->data with only
the min node nd max node.. shd nt we compare the node data with its
left node and right node only.
as it can b a case that node value is greater than min but less than
its left node.. nd here we r nt checking that...
plzzzzzz correct me if i m wrong...........
and is there any other efficient method to find isbst?
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
