## Amazon Interview Question for Software Engineer / Developers

• 0

Country: United States
Interview Type: Phone Interview

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

It can be done as follows:

``````IsValidBST(root,-infinity,infinity);

bool IsValidBST(BinaryNode node, int MIN, int MAX)
{
if(node == null)
return true;
if(node.element > MIN
&& node.element < MAX
&& IsValidBST(node.left,MIN,node.element)
&& IsValidBST(node.right,node.element,MAX))
return true;
else
return false;
}``````

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

You can use same normal BST verification with min and max but at each recursive call, need to check if root->data is not same as left or right data.

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

You can use same normal BST verification with min and max but at each recursive call, need to check if root->data is not same as left or right data.

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

what if the duplicated value is not a child of the corresponding parent node?
will the above method still work?

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

yes it will...the BST property will be violated in that case

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

if duplicates is allowed in BST, then insertion will be with:
i) add new key to left subtree if key is less than or equal to root key
or
ii) add new key to right subtree if key is greater than or equal to root key

Taking (i):
For tree

``````5
3
5
4
5 is root
3 is left to root(5)
next 5 is right to 3
4 is left to 5 (below)

in this tree, 3 is smaller than 5 so in left subtree to 5.
next 5 is less than or equal to root 5 so in left subtree of root (that is 5) and this new 5 is greater than 3 so in right subtree of 3.
So now, 5 is not immediate children of root (5).``````

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

Just take current min and max and check if it is equal to left data or right data return false

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

Can be done with two traversal:

``````First traversal:
Find if any in-order successor of any node is equal to that node to find our duplicate
Second traversal:
Do post order traversal, and each traversal get (min, max) from both subtree and then check for BST property.``````

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

"need to check if root->data is not same as left or right data"
why this check is required at all?
can't we simply go with min/max ..that itself insures that there is no element in left subtree less than or equal to it and similar in right subtree

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

modify the inorder traversal and at each recursive call instead of printing the root, add the root.key into a array with constraint that this root.key> array[lastIndex].

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

Do in-order traversal, items will be in order if BST (if previous items is larger than next, not a BST) and you can check for duplicate by comparing the last item with the next item

One traversal O(n)

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

1) Insert the elements of the tree in to an array doing an inorder traversal
2) Check if the array is sorted and doesnt contain duplicates.

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

We can find the inorder traversal of the tree and check if the data in every left node is less than (not less than or equal to) to the data in it's right node. If it is a BST then the duplicate elements will be consecutive in the inorder traversal.
This is a very simple slution. The inorder traversal can be done either using recursion or the iterative method.

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.