It has been quite sometime since I posted on this blog. Anyways, yesterday a friend asked me this question, given a binary tree (not necessarily Binary Search Tree) find whether it is BST(Binary Search Tree) or not.
Well, the question is pretty straight forward. A small thought on the basic definition of BST will lead us to answer this. As we know, BST holds the property that for every node of the tree its left child (if exists) contains value strictly less than the current node and its right child (if exists) contains value strictly greater than the current code.
Now, if we implement the above logic we may end up marking the below tree as bst which is wrong:-
8
4 10
2 12
A little thought on this reveals the problem with above logic is we are not checking the range for every node. So here goes my C++ implementation (but pretty straight forward. Pardon the syntax errors) with range checking:-
Let the structure of every node is:
struct bst{
int val;
bst *left;
bst *right;
}
So now our function goes:
bool isbst(const bst *T,const int &start, const int &end){
if(!T)
return true; //trivially true for empty tree
if(start <= T->val && T->val <= end){ //check current node lies within range [start,end]
bool left = isbst(T->left, start,T->val-1); //check left subtree is bst
bool right = isbst(T->right, T->val+1,end); //check right subtree is bst
if(left && right)
return true;
}else
return false; //value out of range;
return false; //never reached
}
This function is called like : isbst(root_node, INT_MIN, INT_MAX);
INT_MIN here signifies -infinity and INT_MAX as +infinity
Feedback welcome :)
Posts
We can do using compare the very node value with last value of inorder.
ReplyDeletebool flag=true;
void inorder(tree T,int *lastprinted)
{
if(T==NULL)
{
printf("the tree is empty .Hence, it is a BST\n");
}
else
{
if(T->left!=NULL)
{
inorder(T->left,lastprinted);
}
if(T->data > *lastprinted)
{
*lastprinted=T->data;
}
else
{
printf("the given binary tree is not a BST\n");
flag=false;
exit(0);
}
inorder(T->right,lastprinted);
}
}
I think, there wil be no issues. Point out if any thing is missing here.
Sir,I need you to talk about a recruitment process that amazon has selected me for a supervisor post. They tell me to give a salary of 22000 per month. They have asked for Rs.1650 for dressing. On all documents there is signature of recruitment excutive ANURAG SHARMA. Are you the man? Is this employment is true or a fruad? Please sir share with me.
ReplyDelete@Yogiraj Biplab
DeleteThats not me. It certainly looks like a fraud scam. The companies don't ask for money for recruitment.
Be cautious and stay away from it.