Understanding the Problem
We are given two binary trees. The goal is to determine whether they are isomorphic.
Two trees are said to be isomorphic if they have the same structure and node values,
or if they can be made identical by swapping the left and right children of some nodes.
In simpler terms, two trees are isomorphic if we can transform one into the other by flipping some children
at various levels, without changing any of the node values.
Step-by-Step Solution with Example
Step 1: Understand What We’re Comparing
Let’s say we have two trees:
Tree 1: Tree 2:
1 1
/ / 2 3 3 2
At first glance, they look different because the children are flipped. But if we allow swapping,
they become structurally identical with the same values at corresponding positions. So they are isomorphic.
Step 2: Base Case - Both Trees Are Empty
If both nodes are null
, they are trivially isomorphic. Nothing to compare. Return true.
Step 3: One Node Is Null, Other Is Not
If one of the nodes is null
and the other isn’t, the trees cannot be isomorphic.
A tree with nodes cannot be made to match an empty tree. Return false.
Step 4: Values at the Nodes Differ
If the values stored at the current nodes are different, they can never be isomorphic,
regardless of child swaps. Return false.
Step 5: Check for Isomorphism Recursively
Now comes the real check. We have two possibilities:
- No Swap: Left with left and right with right.
- Swap: Left with right and right with left.
We recursively check both cases. If either results in all corresponding subtrees being isomorphic,
the answer is true.
Step 6: Implement the Recursive Function
boolean isIsomorphic(TreeNode n1, TreeNode n2) {
if (n1 == null && n2 == null) return true;
if (n1 == null || n2 == null) return false;
if (n1.val != n2.val) return false;
boolean noSwap = isIsomorphic(n1.left, n2.left) && isIsomorphic(n1.right, n2.right);
boolean swap = isIsomorphic(n1.left, n2.right) && isIsomorphic(n1.right, n2.left);
return noSwap || swap;
}
Edge Cases
Case 1: Both Trees Are Empty
This is the simplest case. Return true.
Case 2: One Tree Is Empty
Not isomorphic. Return false.
Case 3: Root Values Are Different
No possible swap can make values equal. Return false.
Case 4: Trees Are Exactly the Same
All values and positions match. No swap needed. Return true.
Case 5: Children Are Swapped
Swap makes them match. Return true.
Case 6: Multiple Swaps Needed
If recursive swaps at multiple levels result in match, still return true.
Case 7: Structure Too Different
If number of children, or their arrangement is too different, no amount of flipping helps. Return false.
Finally
Tree isomorphism is all about recursive comparison and being open to flipping children when needed.
For beginners, think of it like trying to align two tangled ropes — you’re allowed to twist one,
but you can’t cut or change their labels. Practice with examples and draw trees to build your intuition.
Comments
Loading comments...