http://geeksforgeeks.org/?p=3042 has all the approaches (right and wrong) for solving this.
On Thu, Jul 1, 2010 at 4:43 AM, divya jain <[email protected]> wrote: > @ 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]<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.
