## Amazon Interview Question for Software Engineer / Developers

Country: India
Interview Type: In-Person

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

for BST:
- Do the inorder traversal on both the trees.
- This will yield sorted sequence
- compare the elements.

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

@ran
i think to compare the values we need to store the value in some array (space required is 2N)........in BST ..........am i correct ????
and for binary trees hash the values of one tree and check for other

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

- We can keep a flag store/compare, so the space required is N
* for the first tree (flag is 'store') we can store the elements in an array
* for the second tree (flag is 'compare') we can just compare with the stored elements

- Yes, for Binary tree we can hash the values.

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

2 different BSTs can have the same inorder ourput.
You'll have to compare the structure explicitly.
Recursively would be easier.

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

I am assuming two trees are same if all the nodes are same with same left/right childs.

Compare roots IF equal, compare left and right and do this recursively.

``````boolean isSame(Node root1, Node root2){
if( (root1==null && root2!=null) || (root2==null && root1!=null))
return false;
if(root1 == null && root2 == null)
return true;
if(root1.data == root2.data)
return(isSame(root1.left,root2.left) && isSame( root1.right,root.right));

return false;
}``````

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

whistle.

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

@bdeesh what is that?

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

kudos.

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

Two trees could give the same inorder traversal and still be not identical. Read up on "Tree rotation".

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

Combining one of Pre-Order & Post-Order Traversal, with In-Order traversal produces a unique tree.

In-order traversal of any BST with same elements will always return same sorted sequence of elements (does not matter what is the construction of tree)

So, with BST we need any one of Pre-Order & Post-Order traversal (In-Order traversal is implicitly those elements in sorted manner)

However, with a binary tree, we would need anyone of In-order & post-order traversal, and In-order traversal.

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

I agree with you. we cannot determine a tree structure unique only using inorder. we need to combine pre-order/ post-order with in-order to produce a unique tree.

In order to solve the problem we need to store inorder sequence in a array and then preorder/postorder in one more array. Then compare both these arrays against second tree.

time complexity would be O(n).
but space complexity would be O(2n).

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

do an in order traversal comparing the vale of key as well depth of key. depth will tel difference in structure and value will tel difference in numbers

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

The first solution is good but it requires extra space for the result of inorder traversal. If the nodes in the tree has a link to their parent, then we can do this in O(N) time and O(1) space. It should be asked from interviewer.

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

If you're allowed extra space, couldn't you just add each node value of the first tree to a hash map? You can add it first with boolean value false, and then with the second tree, you can change them to true as you're traversing it. If you find an element that is not in the hash( or find that a number has been repeated) you can break and return false. If the tree traversal is completed, then you can check the hash to see if any of the values in the hash are still mapped to false. The time complexity should be O(n)...this should work if the given tree isn't a BST as well

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

[EDIT] Wouldn't track duplicates, but you can use count instead of boolean if thats the only issue. thoughts anyone?

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

[EDIT] Wouldn't track duplicates, but you can use count instead of boolean if thats the only issue. thoughts anyone?

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

bool IsStructureSame(node* root1,node* root2)
{
bool bIsSame = false;
if(root1 != nullptr && root2 != nullptr)
{
if(root1->data == root2->data)
{
if(IsStructureSame(root1->pLeft,root2->pLeft))
{
if(IsStructureSame(root1->pRight,root2->pRight))
bIsSame = true;
}
}
}
else if(root1 == nullptr && root2 == nullptr)
bIsSame = true;
return bIsSame;
}

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

The In-order and post-order of the two trees should be identical. Otherwise, they are NOT identical. Both algorithms are O(N) where N is the size of the BST.

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.