Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
Rather simple solution. Do an inorder traversal on the Binary tree. Store the value of the node visited in the prev step and compare. if the current node value is greater than prev node value it is a BST. if the encountered node value is less than the prev value it is not a BST.
This is along the lines unfortunately this is going to crash every time unless your root is null
This is BS. Completely incorrect.
3
/ \
1 4
/
2
If the above figure does not come out correct:
root is 3, has two child nodes 1 and 4. 4 has a left child 2.
The above code will tell it is a BST, while it is not.
Here u go
public static boolean checkBST(node Tree){
Stack<node> s= new Stack<node>();
node tree= Tree;
int prev_val=-999;
while(true){
while(tree!=null){
s.push(tree);
tree=tree.left;
}
if(!s.isEmpty()){
tree=s.pop();
if(tree.data < prev_val) return false;
else{
prev_val=tree.data;
System.out.println(tree.data);
tree=tree.right;
}
}
else break;
}
return true;
}
This fails almost immediately. this tree (which is a bst) fails when it compares node 3 to prev_val set to 5:
5
/ \
3 6
all we need to check is the root node should be greater than the maximum node in the left subtree and it should be less than minimum node of the right subtree then its a binary search tree....
This is the only guy who got it right. For each node 1) Check that left tree has max value less than this node
2)Check that right tree has min value greater than this node.
3)Check that left and right subtrees themselves are BSTs using 1), 2) and leaf check (returns true).
Details of 1) and 2)
For 1) Go to left child and then to it's right child, it's right child (Keep going right until leaf is found) - this is the max.
2) same idea for min on right subtree.
I get your point. But in a binary tree, the max/min value could be on any side of the node. So how are you saying that keep going right till you hit the leaf? So basically we need to traverse each element on both sides of the tree to make sure that max on left side is lesser than parent and min on right side is greater than parent and repeat it for each node.
@SN: Perhaps I didn't word it clearly? I didn't understand the beginning of your comment fully either..but if I understand your statement: "So basically we need to traverse each element on both sides of the tree to make sure that max on left side is lesser than parent and min on right side is greater than parent and repeat it for each node." correctly, then I think we're saying the same thing.
@Anonymous: Your tone seems impolite Anonymous, but I believe it could be provoked by my "This is the only guy who got it right" :P. I apologize if that was rude - didn't mean it to be.
Now to good stuff's answer: I think it is mostly correct, but not 100% correct. A BST will certainly be declared as one, but it is possible a non-BST also gets marked as a BST.
I could be wrong myself as I haven't tested this..but here's what I am thinking:
In the non-recursive part the 2 checks are only:
1. The node in question vs left child's value
2. The node in question vs right child's value
This is insufficient since a node should not only be bigger than it's left child, it should be bigger than the entire sub-tree rooted at the left child.
Similar idea for the right child.
I don't think the recursion ever takes care of that.
So basically a tree like this : 9
5 12
4 11
I think when 9 and 5 are compared it will be true and the fact that 11 is hiding under the left tree of 9 will never be caught.
//without the inorder traversal...
int find_max(NODEPTR root)
{
//using level order traversal we can find maximum
}//end of find max
int find_min(NODEPTR root)
{
//using level order traversal we can find minimum
}//end of find minimum
int check(NODEPTR root,int*max,int*min)
{
if(root==NULL)
return 1;
if(root->data>find_max(root->left))
{
if(root->data<find_min(root->right))
{
return(check(root->left)&&check(root->right));
}
else
return 0;
}
return 0;
}
CAN ANYONE SUGGEST SOMETHING BETTER SUCH THAT WE DON'T HAVE TO CALCULATE MAX AND MINIMUM FOR A NOE AGAIN AND AGAIN
Solution with complexity O(n):
bool isBST(node * ptr, int min, int max)
{
if(ptr == 0)
return TRUE;
if(ptr->val < min || ptr->val > max)
return FALSE;
return (isBST(ptr->left,min,ptr->val -1) == TRUE
&& isBST(ptr->right, ptr->val, max) == TRUE)
}
int main()
{
check = isBST(root, INT_MIN , INT_MAX)
}
- Good Stuff October 03, 2012