## Amazon Interview Question Software Engineer / Developers

• 0

Two trees are given. Write a function to check if both of these trees are isotropic. Isotropic trees are those, when flipping few of the child nodes of a tree make both the trees equal. For e.g
.......1......
...2.......3.
.........4...5

......1.......
...3.......2..
.4....5.......

both of these are isotropic. If we flip the node with value 2 and 3 in the second tree then both trees will be equal.

Country: India

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.
3
of 3 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.
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 walking you through every aspect of getting a job at a top tech company, while focuses on software engineering interviews.

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