[GeeksForGeeks] Check if two trees are Isomorphic

Write a function to detect if two trees are isomorphic. Two trees are called isomorphic if one of them can be obtained from other by a series of flips, i.e. by swapping left and right children of a number of nodes. Any number of nodes at any level can have their children swapped. Two empty trees are isomorphic.

Algorithm

Two trees are isomorphic in the following 2 cases.

1. both trees are null;

2. 　a.neither tree is null;

　　 b.their roots' values are the same;

　　 c. either tree 1's left subtree is isomorphic with tree 2's left subtree and tree 1's right subtree is isomorphic with tree 2's right subtree;

or tree 1's left subtree is isomorphic with tree 2's right subtree and tree 1's right subtree is isomorphic with tree 2's left subtree.

The above algorithm is a natural statement for solving this problem recursively.

 1 public class IsomorphicTree {
 2     public boolean isIsomorphicTree(TreeNode root1, TreeNode root2) {
 3         if(root1 == null && root2 == null) {
 4             return true;
 5         }
 6         else if(root1 == null || root2 == null) {
 7             return false;
 8         }
 9         else if(root1.val != root2.val) {
10             return false;
11         }        
12         return (isIsomorphicTree(root1.left, root2.left) && isIsomorphicTree(root1.right, root2.right))
13                 || (isIsomorphicTree(root1.left, root2.right) && isIsomorphicTree(root1.right, root2.left));
14     }
15 }

The runtime of this solution is O(m + n), m and n are the number of nodes in tree 1 and 2.