Tree Isomorphism Problem

Problem Statement

Given two binary trees, check if they are isomorphic. Two trees are called isomorphic if one can be obtained from the other by a series of flips, i.e., by swapping left and right children of some nodes. The values in the nodes are not changed.

Example 1:

Example 2:

Approach 1: Brute Force (Try All Flip Combinations)

Intuition

At each node, we can either flip children or not. Try both possibilities and see if either leads to identical trees.

Algorithm

1. If both nodes are null, they're isomorphic
2. If one is null or values differ, not isomorphic
3. Check two cases:
   • No flip: left1 matches left2 AND right1 matches right2
   • Flip: left1 matches right2 AND right1 matches left2
4. If either case works, trees are isomorphic

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public boolean isIsomorphic(TreeNode root1, TreeNode root2) {
        // Both empty
        if (root1 == null && root2 == null) {
            return true;
        }
        
        // One empty, one not
        if (root1 == null || root2 == null) {
            return false;
        }
        
        // Values must match
        if (root1.val != root2.val) {
            return false;
        }
        
        // Check both possibilities: flip or no flip
        // Case 1: No flip - left matches left, right matches right
        boolean noFlip = isIsomorphic(root1.left, root2.left) &&
                         isIsomorphic(root1.right, root2.right);
        
        // Case 2: Flip - left matches right, right matches left
        boolean withFlip = isIsomorphic(root1.left, root2.right) &&
                           isIsomorphic(root1.right, root2.left);
        
        return noFlip || withFlip;
    }
}

Complexity Analysis

• Time Complexity: O(n * m) - In worst case, may need to explore many combinations
• Space Complexity: O(n + m) - Recursion stack

Approach 2: Optimal (Early Termination)

Intuition

The brute force approach is already quite efficient. We optimize by checking the no-flip case first (more common), and using short-circuit evaluation to avoid unnecessary comparisons.

Algorithm

1. Base cases remain the same
2. Try no-flip first (statistically more likely in many cases)
3. Only try flip case if no-flip fails
4. Use short-circuit evaluation

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public boolean isIsomorphic(TreeNode t1, TreeNode t2) {
        // Both null
        if (t1 == null && t2 == null) return true;
        
        // One null
        if (t1 == null || t2 == null) return false;
        
        // Values differ
        if (t1.val != t2.val) return false;
        
        // Try no-flip first (short-circuit if true)
        if (isIsomorphic(t1.left, t2.left) && 
            isIsomorphic(t1.right, t2.right)) {
            return true;
        }
        
        // Try flip
        return isIsomorphic(t1.left, t2.right) && 
               isIsomorphic(t1.right, t2.left);
    }
}

Iterative BFS Approach

Complexity Analysis

• Time Complexity: O(min(n, m)) - We stop as soon as we find a mismatch
• Space Complexity: O(min(n, m)) - Recursion stack or queue size

Key Takeaways

1. Isomorphism definition: Trees that can be made identical by swapping children
2. Two possibilities at each node: Either flip children or don't
3. Values must match: Even after flipping, corresponding nodes must have same values
4. Short-circuit evaluation: Try likely case first, avoid unnecessary work
5. Related problems: Tree isomorphism has applications in graph theory, chemistry (molecular structure matching)