@Don,
Your method fails for the case below:
//Check if a binary tree is Binary Search Tree or not.
#include<stdio.h>
typedef struct node
{
int value;
struct node *left,*right;
}nodeptr;
nodeptr *newnode(int x)
{
nodeptr* tmp = (nodeptr*)malloc(sizeof(nodeptr));
tmp->value=x;
tmp->left=NULL;
tmp->right=NULL;
return tmp;
}
int isBinTree(struct node *t)
{
return (!t) || ((!t->left || (t->value > t->left->value)) &&
(!t->right || (t->value < t->right->value)) &&
isBinTree(t->left) && isBinTree(t->right));
}
int main()
{
/*
This is not a BST
50
/ \
40 60
\
55
*/
nodeptr *root=NULL;
root = newnode(50);
root->left = newnode(40);
root->right=newnode(60);
root->left->right = newnode(55);
printf("%s\n",isBinTree(root)?"It is a BST":"It is not a BST");
}
On Tue, Nov 6, 2012 at 3:10 AM, shady <[email protected]> wrote:
> Understood, thanks.
>
>
> On Tue, Nov 6, 2012 at 2:35 AM, Don <[email protected]> wrote:
>
>> In English, that is
>>
>> A null tree is a binary tree.
>> Otherwise, it's a binary tree if the root value is greater than the
>> left child and less than the right child, and the left and right
>> subtrees are binary trees.
>>
>> Don
>>
>> On Nov 5, 2:48 pm, Don <[email protected]> wrote:
>> > That would work. But a simpler approach is:
>> >
>> > bool isBinTree(root *t)
>> > {
>> > return (!t) || ((!t->left || (t->value > t->left->value)) &&
>> > (!t->right || (t->value < t->right->value)) &&
>> > isBinTree(t->left) && isBinTree(t->right));
>> >
>> > }
>> >
>> > On Nov 5, 2:04 pm, shady <[email protected]> wrote:
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> > > Hi,
>> > > Can we check this by just doing an inorder traversal, and then
>> checking if
>> > > it is in increasing order or not ?
>>
>> --
>> 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.
>>
>>
> --
> 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.
>
--
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.
