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].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
