CareerCup

the checkbst returns 1 if tree is BST and return zero otherwise

int checkbst(struct node*node,int min,int max)//initial call is with min=INT_MIN and // max=INT_MAX
{
if (node==NULL) return 1;
if(node->data < min ||node->data>max) return 0;
return(checkbst(node->left,min,node->data && checkbst(node->right,node->data,max);
}

do in-order traversal and check if the sequence is increasing

int isBST(struct node *ele)
{
if(node==NULL) return 1;
else if(node->left->value > node->value || node->right->value < node->value) return 0;
else return(isBST(node->left) && isBST(node->right))
}

int isBST(struct node *ele)
{
if(node==NULL) return 1;
else if(node->left->value > node->value || node->right->value < node->value) return 0;
else return(isBST(node->left) && isBST(node->right))
}

int isBST(struct node *ele)
{
if(node==NULL) return 1;
else if(node->left->value > node->value || node->right->value < node->value) return 0;
else if ((node->left == NULL) && (node->right == NULL)) return 1;
else return(isBST(node->left) && isBST(node->right))
}

The codes above would crash if node->left is NULL when you access node->left->value.
also it doesn't consider the case where the BST is not complete.

A more complete version is

bool isBST(bnode * root)
{
if(root == NULL)
return true;
else if((root->left == NULL)||(root->left == NULL))
{
if((root->left == NULL)&&(root->left == NULL))
return true;
else if((root->left==NULL)&&(root->id >= root->right->id))
return false;
else if ((root->right==NULL)&&(root->id < root->left->id))
return false;
}
else if((root->id < root->left->id) ||(root->id >= root->right->id))
return false;
else
return (isBST(root->left) && isBST(root->right));
}

Above algos are not correct, by just checking left and right child we can not be sure that it is a BST, we have to ensure that all the elements on right are bigger then the current node and all the elements on the left are smaller then the current one.

We can do this by passing minimum and maximum values while using recursion, search on google you will find the solution.

I liked the comment of bewda...

i think recursive solution is far better

a better solution:

bool isthisBST(nodeptr root)
{
return isthisBSTUtil(root,INT_MIN, INT_MAX);
}

int isthisBSTUtil(nodeptr root, int min, int max)
{
if(root == NULL) return true; //empty tree is a bst
if(root-data < min || root->data >max) return false;

return (isthisBSTUtil(root->left, min, root->data) || isthis BSTUtil(root->right,root->data, max);
}

NOte: we call isthisBST(root,INT_MIN,INT_MAX);