Re: [algogeeks] Re: isbst
@Divya Jain: In the algorithm I gave, please note that, the *max value in left subtree* should be *smaller than* the current node's key, which inturn should be *smaller than* the *min value in right subtree*. That way, my algorithm would return "false" for the example which you gave. On Sun, Jul 4, 2010 at 1:46 PM, sharad kumar wrote: > @dheeraj > for this tree inorder is 12 14 13 > first 12 comes,it is saved in temp > now 14 comes since 14>12 so temp =14 > now when 13 comes which is less than temp hence not a bst > correct me if i wrong > > -- > 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. > -- 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.
Re: [algogeeks] Re: isbst
@dheeraj for this tree inorder is 12 14 13 first 12 comes,it is saved in temp now 14 comes since 14>12 so temp =14 now when 13 comes which is less than temp hence not a bst correct me if i wrong -- 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.
Re: [algogeeks] Re: isbst
@Dheeraj: It would return false. Initially temp=12, next temp=14, then it'll
compare 13 wrote:
> @Raj N
> It won't work for the tree like. your method would return true for the
> following tree.
>
> 13
> /
> 12
>\
>14
>
>
>
>
> On Sat, Jul 3, 2010 at 3:45 AM, Raj N wrote:
>
>> According to me perform inorder traversal and at every point store the
>> current element in a temporary variable and check if the next element
>> obtained is greater than temp otherwise return false
>>
>> int temp=-;
>> int flag=1;
>> void isBst(NODE *tree)
>> {
>> if (tree!=NULL)
>> {
>> isBst(tree->left);
>> if (tempinfo)
>> temp=tree->info;
>> else
>> {
>> flag=0;
>> return;
>> }
>> isBst(tree->right);
>> }
>> }
>>
>> Please correct me if I'm wrong
>>
>>
>> On Fri, Jul 2, 2010 at 6:43 PM, sharad kumar wrote:
>>
>>> i read that link ,i dont think that is very efficient,someone plzzz look
>>> at that soln n comment
>>> bcoz i m really confused in this isbst ques so plzzz
>>>
>>> --
>>> 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.
>>>
>>
>> --
>> 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.
>>
>
> --
> 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.
>
--
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.
Re: [algogeeks] Re: isbst
@Raj N
It won't work for the tree like. your method would return true for the
following tree.
13
/
12
\
14
On Sat, Jul 3, 2010 at 3:45 AM, Raj N wrote:
> According to me perform inorder traversal and at every point store the
> current element in a temporary variable and check if the next element
> obtained is greater than temp otherwise return false
>
> int temp=-;
> int flag=1;
> void isBst(NODE *tree)
> {
> if (tree!=NULL)
> {
> isBst(tree->left);
> if (tempinfo)
> temp=tree->info;
> else
> {
> flag=0;
> return;
> }
> isBst(tree->right);
> }
> }
>
> Please correct me if I'm wrong
>
>
> On Fri, Jul 2, 2010 at 6:43 PM, sharad kumar wrote:
>
>> i read that link ,i dont think that is very efficient,someone plzzz look
>> at that soln n comment
>> bcoz i m really confused in this isbst ques so plzzz
>>
>> --
>> 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.
>>
>
> --
> 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.
>
--
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.
Re: [algogeeks] Re: isbst
According to me perform inorder traversal and at every point store the
current element in a temporary variable and check if the next element
obtained is greater than temp otherwise return false
int temp=-;
int flag=1;
void isBst(NODE *tree)
{
if (tree!=NULL)
{
isBst(tree->left);
if (tempinfo)
temp=tree->info;
else
{
flag=0;
return;
}
isBst(tree->right);
}
}
Please correct me if I'm wrong
On Fri, Jul 2, 2010 at 6:43 PM, sharad kumar wrote:
> i read that link ,i dont think that is very efficient,someone plzzz look at
> that soln n comment
> bcoz i m really confused in this isbst ques so plzzz
>
> --
> 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.
>
--
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.
Re: [algogeeks] Re: isbst
i read that link ,i dont think that is very efficient,someone plzzz look at that soln n comment bcoz i m really confused in this isbst ques so plzzz -- 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.
Re: [algogeeks] Re: isbst
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 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 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 wrote:
>>
>>> just do one thing print inorder. if sorted it is a BST
>>>
>>> On Jun 19, 2:57 pm, divya 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...
>>> >
>>> > plzz 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
>>> .
>>> 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.
>>
>
> --
> 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.
>
--
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.
Re: [algogeeks] Re: isbst
@ 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 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 wrote:
>
>> just do one thing print inorder. if sorted it is a BST
>>
>> On Jun 19, 2:57 pm, divya 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...
>> >
>> > plzz 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
>> .
>> 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.
>
--
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.
Re: [algogeeks] Re: isbst
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 wrote:
> just do one thing print inorder. if sorted it is a BST
>
> On Jun 19, 2:57 pm, divya 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...
> >
> > plzz 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
> .
> 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.
[algogeeks] Re: isbst
just do one thing print inorder. if sorted it is a BST
On Jun 19, 2:57 pm, divya 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...
>
> plzz 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.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
