Amazon Interview Question
Software Engineer / DevelopersTeam: Kindle-Periodicals
Country: India
Interview Type: In-Person
A binary tree is a BST if each of the right and left nodes of the node is a BST. So this can be recursively as,
bool isBST(node *root)
{
if (root == NULL)
return true;
else
{
if(root->left-->data <= root-->data < root-->right-->data)
{
return( isBST(root-->left) && isBST(root-->right))
}
else
{
return false;
}
}
}
Method I - There is a necessity that there be a global element ( say a static element). This value shall point to the previous value in the inorder traversal. We need to check if the current value's data is greater than that of the previous data.
Method II - We can insert values into a stack as we go along with the inorder traversal. If the current value is greater than the peek of the stack..we check further till end. Otherwise return false.
Method III - We can put all the elements of the tree in an array ( in order traversal ofcourse) and then check if it is in an increasing order.
Traverse the tree in-order and save each element in an array.
- Prafull March 18, 2012If the array is sorted, the binary tree is a BST