Amazon Interview Question
Software Engineer / DevelopersCountry: India
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.
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.
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.
@upgrade_server
Can you please tell if there is any restriction of data in the question?
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)) )
}
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;
}
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.
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))
- guneesh June 23, 2012