What is Tree Isomorphism?
Two trees are considered isomorphic if one tree can be transformed into the other by swapping the left and right children of a number of nodes (including potentially zero swaps). Essentially, they represent the same structure if we ignore the left/right ordering of children.
Visual Example
These trees are isomorphic. If you swap the children of node 1, and then swap the children of node 2, they become identical.
Algorithm Strategy
1. Value Equality
First check if both nodes are null (return true) or if only one is null or values differ (return false).
2. Check Non-Swapped
Assume the children were NOT swapped. Recursively verify if `root1.left` is isomorphic to `root2.left`, AND `root1.right` is isomorphic to `root2.right`.
3. Check Swapped
Assume the children WERE swapped. Recursively verify if `root1.left` is isomorphic to `root2.right`, AND `root1.right` is isomorphic to `root2.left`. Return true if either the swapped or non-swapped check passes.
Complexity Analysis
Where N1/N2 are the number of nodes, and H1/H2 are the heights. In the worst case (e.g. perfect binary trees), time could be O(N^2) if not optimized, but practically bounds are close to O(N) for unbalanced comparisons.
Time Complexity: O(min(M, N))
Key Takeaways
- Isomorphism is a classic example of "try both possibilities" recursion. We branch into two possibilities at every step: swapped and unswapped.
- Because of short-circuit evaluation (`||` and `&&`), the recursion often stops early if structural mismatches are found.