|
Algo to check if given binary tree is binary search tree or not .....
Microsoft Interview Questions and Answers
(Continued from previous question...)
276. Algo to check if given binary tree is binary search tree or not .....
Question:
Algo to check if given binary tree is binary search tree or not. Code it and return true or false. Also it should find the number of nodes in the tree irrespective if the tree is BST or not.
maybe an answer:
Just Inorder traverse the tree and determine the preNode < currentNode is fine
PNode IsBSTCore(PTree tree, PNode &pPreNode)
{
if(tree)
{
PNode pNode = IsBSTCore(tree->left, pPreNode);
if(pNode) return pNode;
if(pPreNode && pPreNode->data > tree->data)
{
return tree;
}
printf("%d\t%d\t", pPreNode? pPreNode->data : -1, tree->data);
pPreNode = tree;
pNode = IsBSTCore(tree->right, pPreNode);
return pNode;
}
return tree;
}
PNode IsBST(PTree tree)
{
assert(tree != NULL);
PNode pNode = NULL;
return IsBSTCore(tree, pNode);
}
(Continued on next question...)
Other Interview Questions
| 