i think that you're right
the test case that this code fails at is not hard to find
but if you just check (as you mentioned)
for each node
whether the values of its left child and right child are acceptable
its left subtree and right subtree are bst
this algorithm runs in O(V) which is the best possible running time since we
have to check each node at least once
plz correct me if I'm wrong
On Sat, Jun 19, 2010 at 2:27 PM, divya <sweetdivya....@gmail.com> wrote:
> 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 algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
