CareerCup

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.

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;
}

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))