@ above
here u r comparing node value with min and max only
for eg if ur tree is
45
/ \
65 85
/
25
ur code will say that this is bst. bt it is not
plzz correct me if i m wrong..
On 1 July 2010 16:17, CM Saikanth Varma <[email protected]> wrote:
> Hi,
>
> The idea is like this:
>
> Isbst(node *t){
> if(t==NULL){ return true; }
> if ( Isbst(t->left) &&
> Isbst(t->right) &&
> (maxValue(t->left) <=(t->data) ) &&
> (minValue(t->right) >= (t->data)
> )
> return true;
> else
> return false;
> }
>
> I hope it makes sense :D
> On Thu, Jul 1, 2010 at 3:37 PM, vicky <[email protected]> wrote:
>
>> just do one thing print inorder. if sorted it is a BST
>>
>> On Jun 19, 2:57 pm, divya <[email protected]> wrote:
>> > i have found the following code on net to check if the binarytreeis
>> > bst or not
>> > /*
>> > Returns true if a binarytreeis a binary searchtree.
>> > */
>> > 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 oftree..
>> >
>> > 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]<algogeeks%[email protected]>
>> .
>> 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 [email protected].
> To unsubscribe from this group, send email to
> [email protected]<algogeeks%[email protected]>
> .
> 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 [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.
