## Amazon Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
6
of 6 vote

``````bool FindIfIsBST()
{
return isbst(root, Integer.MIN, Integer.MAX)
}

bool isbst(node n, int p, int q)
{
if(n == null)
return true;

if(n.data > p && n.data < q && isbst(n.left, p, n.data)
&& isbst(n.right, n.data, q))
return true;

return false;
}``````

Comment hidden because of low score. Click to expand.
0

Good stuff!

Comment hidden because of low score. Click to expand.
0

There is a bug in the code. When comparing n.data with p and q, we should use ">=" and "<=" instead of ">" & "<". Other wise, the BST like below is returned false.

``````0
-5  7
-5 0 0 7``````

Comment hidden because of low score. Click to expand.
4
of 4 vote

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.

Comment hidden because of low score. Click to expand.
0

agree

Comment hidden because of low score. Click to expand.
0

this algorithm is good, but needs a global variable to hold the prev node value if using recursion.

Comment hidden because of low score. Click to expand.
1
of 3 vote

This comment has been deleted.

Comment hidden because of low score. Click to expand.
0

LOL!

Comment hidden because of low score. Click to expand.
0

This is along the lines unfortunately this is going to crash every time unless your root is null

Comment hidden because of low score. Click to expand.
0

what u mean by it crash ???

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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;
}``````

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

No it will not when it pops out 3 from stack prev_val will be -999 not 5 try running it

Comment hidden because of low score. Click to expand.
1
of 1 vote

Node prev = new Node(null,null,0);
boolean isBST(Node n)
{
if(n == null)
return true;
boolean flag = isBST(n.left);
if(prev.value>n.value)
return false;
prev = n;
System.out.println(n.value);
boolean flag1 =isBST(n.right);
return flag&flag1;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

This comment has been deleted.

Comment hidden because of low score. Click to expand.
0

LOL!

Comment hidden because of low score. Click to expand.
0
of 0 vote

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....

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

@fizzybuzzer: Don't be so blind. Read good stuff's answer. You might learn something.

Comment hidden because of low score. Click to expand.
0

@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.

Comment hidden because of low score. Click to expand.
0

Just noticed my example tree got completely Fed. Attempt #2:

------------9-----------
----------/----\---------
---------5----12------
-------/--\--------------
-----4---11-----------

Comment hidden because of low score. Click to expand.
0
of 0 vote

//the inorder array stores inorder traversal and we can check whether they are sorted or not..

int check(NODEPTR root,int in_order[],int n)
{
for(i=0;i<n-1;i++)
{
if(in_order[i]>in_order[i+1])
return -1;
}
return 1;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

in the above code we don't need pointer to root of BT

Comment hidden because of low score. Click to expand.
0
of 0 vote

//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

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0
of 0 vote

TC : O(n) , SC : O(n)
Do in-order traversal of tree and store each node value in array.
Again traverse through the array to check a[i] < a[i+1] ...
if true for all .... Yes else No.

Comment hidden because of low score. Click to expand.
0
of 0 vote

isBST(node *root,node *prev)
{
isBST(root->left,prev);
if(prev==NULL)
prev->data=root->data;
else
{
if(prev->data > root->data)
{ printf("not bst");
exit;
}
else
prev->data=root->data;
}
isBST(root->right,prev);
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Collapse the tree in an array by Left-root-Right traversing and check if it is sorted array, if sorted answer is BST otherwise not a BST

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0

Yay!

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.