How to identify, whether two trees are isomorphic or not?

Question

This was asked today at Amazon interview -

Given two Binary Trees (not BST). Each node of both trees has an integer value. Validate whether both trees have the same integers, there could be repetitive integers.

Example
Tree1:
5
1 6
5 4 3 6

Tree2:
1
3 4
6 5

Output
Identical integers

Sample C/C++/Java code would be helpful.

Answer 1

1. A tree with a single node is isomorphic only to a tree with a single node.

2. Two trees with roots A and B, none of which is a single-node tree, are isomorphic if and only if there is a 1-1 correspondence between the subtrees of A and of B such that the corresponding subtrees are isomorphic.

   int checkIsomorphism(root_tree1, root_tree2)
   {
   if ( root_tree1==Null && root_tree2==NULL)
   return 1
   else if (root_tree1==NULL)
   return 0
   else if (root_tree2==NULL)
   return 0
   else if (root_tree1->data!=root_tree2->data)
   return 0
   else
   return (checkIsomorphism(root_tree1->left,root_tree2->right) && checkIsomorphism(root_tree1->right,root_tree2->left)) || (checkIsomorphism(root_tree1->left,root_tree2->left) && checkIsomorphism(root_tree1->right,root_tree2->right)
   }

//Asumption checking for binary trees

The condition for two trees to be Isomorphic is that ---
Given the root of first tree say X and root of second tree say Y, The subtrees must be isomorphic(All the four subtrees.....two in first and two in second) and there must be one to one correspondence between subtrees of X and subtres of Y. What it mean is that whether the (1) left subtree of X is isomorpic with right subtree of Y And right subtree of X is isomorpic with left subtree of Y OR (2) left subtree of X is isomorpic with left subtree of Y And right subtree of X is isomorphic with right subtree of Y. One among 1 or 2 must be two.. One to One correspondance for binary trees (2-ary) has this meaning. For K- ary There are K! different conditions which need to be checked for Isomorphism