Amazon Interview Question
Software Engineer / DevelopersTeam: Chennei
Country: India
Interview Type: Written Test
This question can be easily misinterpreted. The conditioin
left_child < node < right_child
is not enough to make a binary tree a BST. Given a node n, all descendants to the left must be less than n's value. Likewise, all descendants to the right must be greater than n's value. These bounds must be passed forward in the search.
int check_bst(Node *p, int min, int max)
{
if (p == 0)
return 1;
int value = p->value;
if (value > max || value < min)
return 0;
return check_bst(p->left, min, value-1)
&& check_bst(p->right, value+1, max);
}
int is_bst(Node *root)
{
int value = root->value;
return check_bst(root->left, INT_MIN, value-1)
&& check_bst(root->right, value+1, INT_MAX);
}
int min = minimum value of integer
int max = maximum value of integer
isBST(Tree node, min, max );
//actual method implementation
isBST(Tree node, int min, int max){
if(node==null)
return true;
if(node.value > min || node.value < max)
return false;
return isBST(node.left,min,node.data-1)&&isBST(node.right,node.data+1,max);
}
/* C# Code */
bool result = IsBST(root, MIN, MAX);
private bool IsBST(TreeNode node, int min, int max)
{
if (node == null)
{
return true;
}
if (node.Value < min || node.Value > max)
{
return false;
}
Debug.WriteLine(string.Format("Current: {0} \t Left: {1} \t Right: {2}", node.Value, node.Left == null ? -1 : node.Left.Value, node.Right == null ? -1 : node.Right.Value));
bool leftBST = false;
bool rightBST = false;
if (node.Left == null || node.Value > node.Left.Value)
{
leftBST = true;
}
if (node.Right == null || node.Value < node.Right.Value)
{
rightBST = true;
}
if (leftBST && rightBST)
{
return IsBST(node.Left, min, node.Value) && IsBST(node.Right, node.Value, max);
}
else
{
return false;
}
}
static class Node {
public Node left;
public Node right;
public int data;
}
public boolean isBst(Node node)
{
return isBinarySearchTree(node , Integer.MIN_VALUE , Integer.MAX_VALUE);
}
public boolean isBinarySearchTree(Node node , int min , int max)
{
if(node.data < min || node.data > max)
return false;
//Check this node!
//This algorithm doesn't recurse with null Arguments.
//When a null is found the method returns true;
//Look and you will find out.
/*
* Checking for Left SubTree
*/
boolean leftIsBst = false;
//If the Left Node Exists
if(node.left != null)
{
//and the Left Data are Smaller than the Node Data
if(node.left.data < node.data)
{
//Check if the subtree is Valid as well
leftIsBst = isBinarySearchTree(node.left , min , node.data);
}else
{
//Else if the Left data are Bigger return false;
leftIsBst = false;
}
}else //if the Left Node Doesn't Exist return true;
{
leftIsBst = true;
}
/*
* Checking for Right SubTree - Similar Logic
*/
boolean rightIsBst = false;
//If the Right Node Exists
if(node.right != null)
{
//and the Right Data are Bigger (or Equal) than the Node Data
if(node.right.data >= node.data)
{
//Check if the subtree is Valid as well
rightIsBst = isBinarySearchTree(node.right , node.data+1 , max);
}else
{
//Else if the Right data are Smaller return false;
rightIsBst = false;
}
}else //if the Right Node Doesn't Exist return true;
{
rightIsBst = true;
}
//if both are true then this means that subtrees are BST too
return (leftIsBst && rightIsBst);
}
- Vir Pratap Uttam May 05, 2015