## Amazon Interview Question for Software Engineer / Developers

Country: India

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

bool isotropic(root *t1,root *t2)
{
if(t1==Null&&t2==NULL)
return true;

if(t1==Null||t2==nULL)
return false;

if(t1->data!=t2->data)
return false;

if(t1->left==t2->left)
{
return isotropic(t1->left,t2->left)&&(t1->right,t2->right);
}
else if(t1->left==t2->right)
{
return isotropic(t1->left,t2->right)&&(t1->right,t2->left);
}
else
return false;
}

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

clear and precise but lot of extra memory will be used. call stack though you are not using explicitly but your program do, but liked the solution had a similar approach but explicitly using stack.

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

t1->left.Data==t2->left.Data

and else if(t1->left.Data==t2->right.Data)

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

Assuming your code is in C, please elaborate on how pointer comparison works. For instance

t1->left == t2->left

. I guess you meant to do

t1->left->data == t2->left->data

. But in that case we would have to first check if

t1->left and t2->left

are not null.

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

I may or may not be understanding the definition of 'isotropic' correctly, but if I understand correctly, I think two trees will be isotropic iff each node has the same parent in one tree as in the other tree. So we'd just have to check that every node has the same parent. As we read through a tree we could simply record in an array the parent node of each value (or in a HashMap depending on how the info is given) and then read through the second tree and check that the info matches up.

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

Eugene,

Your analysis will hold true as long as there is no duplicate data in the tree. Since this is a binary tree, hence duplicates might exist, and they will exist with different parents.

Can you please tell if there is any restriction of data in the question?

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

I got the impression nodes would actually be labeled 1 through N. I admit the question was unclear.

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

isIsotropic(root1,root2)
{
if(!root1 && !root2)
return true;
if(!root1 || !root2)
return false;
return root1->data==root2->data && ( (isIsotropic(root1->left,root2->left) && isIsotropic(root1->right,root2->right)) || (isIsotropic(root1->left,root2->right) && isIsotropic(root1->right,root2->left)) )
}

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

Like

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

This looks correct !

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

If there are no repeated nodes and nodes in the tree has a link to the parent the Eugene solution is just perfect (+1 from me).
Still if the tree has no link to the parent or the tree can have repeated nodes we have to traverse all the possible combinations. Here is the java code for that

public boolean isIsotropicBT(TreeNode t1, TreeNode t2) {
boolean result = false;
if (t1 ==null && t2 == null)
result = true;
else if (t1 != null && t2 != null && t1.data == t2.data) {
result = isIsotropicBT(t1.left, t2.left) && isIsotropicBT(t1.right, t2.right);
result |= isIsotropicBT(t1.left, t2.right) && isIsotropicBT(t1.right, t2.left);
}

return result;
}

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

Consider each tree as logically composed of

unordered list of leaf nodes + subtree without leaf nodes.

If both properties are identical, then trees are isotropic.

Would need additional space equal to the number of leaf nodes.

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

/ignore ;) Isotropic needs to be defined more accurately

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

If the nodes are comparable(have some ordering property)

then we can use 'ViX' traversal where we visit child nodes in ascending/descending order.

Isotropic trees should result in identical nodes at each step.

(This is if I finally understand isotropic trees))

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

ViX traversal for

0
|
___
| |
A B

would be OAB if A>B and OBA if B>A

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.