Solution:

If the given binary tree is a Binary search tree,then the inorder traversal should output the elements in increasing order.We make use of this property of inorder traversal to check whether the given binary tree is a BST or not.We make note of the latest element that could have been printed and compare it with the current element.Given below is a C function to check it.

bool 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);

}

}

Now check the value of flag to say whether it is a BST or not.If it is not then it is already taken care by the code.

__Click Here For More Questions__

had i known this before, i would have saved my google interview

ReplyDeleteby using level order traversal and checking each node for BST property can also be a solution for this problem

ReplyDeletewrong solution

ReplyDelete