medium Isomorphic Trees

Problem Statement

Given root of two binary trees root1 and root2, return true if they are isomorphic. Otherwise, return false.

Two trees are said to be isomorphic if one tree can be transformed into the other by swapping the left and right children of some nodes.

Note that the structure should be identical after possible swaps, and the values of nodes must be the same in both trees.

Examples

Example 1

• Input: root1 = [1, 2, 3, 4], root2 = [1, 3, 2, null, null, 4]

• Output: true
• Explanation: In the first tree, we can swap 2 with 3, and 4 with null to get the second tree by swapping.

Example 2

• Input: root1 = [1, 2, 3], root2 = [1, 3, 2]

• Output: true
• Explanation: We can swap the left and right children of the root node in Tree 1. This transforms Tree 1 into Tree 2.

Example 3

• Input: root1 = [1, 2, 3, 4, 5, 6, 7], root2 = [1, 4, 3, 2, 5, 7, 6]

• Output: false
• Explanation: We can't get tree2 by performing swap operations in tree1.

Solution

To solve this problem, we will use Depth-First Search (DFS) to compare both trees node by node. The key is to check if the current nodes in both trees match and then recursively verify their children. If they can be swapped and still match, the trees are isomorphic. Our approach focuses on exploring both possibilities: when the left children match with the left children, and when the left children match with the right children (after a swap). This approach is effective as it directly handles the recursive nature of trees and the swap condition, ensuring that we cover all potential transformations.

DFS ensures that we explore all nodes and their children thoroughly. This is important because both the structure and values of the trees must match after considering possible swaps at each node.

Step-by-Step Algorithm

1. Base Case 1:

   • Check if both root1 and root2 are null.
   • If both trees are empty, return true because two empty trees are considered isomorphic.

2. Base Case 2:

   • Check if either root1 or root2 is null.
   • If one tree is empty and the other is not, return false because one tree being non-existent makes them non-isomorphic.

3. Compare Node Values:

   • Compare the values of the current nodes (root1.val and root2.val).
   • If their values do not match, return false because nodes with different values cannot be considered isomorphic.

4. Recursive Check without Swap:

   • Check if the left child of root1 is isomorphic to the left child of root2 and the right child of root1 is isomorphic to the right child of root2.
   • This is the scenario where no swapping occurs. Call the isIsomorphic() function recursively for both left and right subtrees.

5. Recursive Check with Swap:

   • Check if the left child of root1 is isomorphic to the right child of root2 and the right child of root1 is isomorphic to the left child of root2.
   • This is the scenario where swapping occurs. Call the isIsomorphic() function recursively with swapped children.

6. Final Check:

   • If either of the checks (with or without swap) returns true, then the trees are isomorphic. Return true.
   • If both checks return false, then the trees are not isomorphic. Return false.

Algorithm Walkthrough

Example Input:

• root1 = [1, 2, 3, 4]
• root2 = [1, 3, 2, null, null, null, 4]

1. Step 1: Start by comparing the root nodes of both trees:

   • root1.val = 1
   • root2.val = 1
   • Since the values are equal, we proceed to check the children.

2. Step 2: First, we try comparing the children without any swaps:

   • Compare root1.left (value 2) with root2.left (value 3).
     • Check 1: 2 != 3, so the comparison without swaps fails.
   • Compare root1.right (value 3) with root2.right (value 2).
     • Check 2: 3 != 2, so the comparison without swaps fails completely.

3. Step 3: Since comparing without swaps failed, we now try comparing the trees with a swap:

   • Compare root1.left (value 2) with root2.right (value 2).
     • Check 3: 2 == 2, so the values match. Now, we need to compare their respective children.

4. Step 4: Now, compare the subtrees of root1.left and root2.right. Start by comparing without swap for this subtree:

   • Compare root1.left.left (value 4) with root2.right.left (null).
     • Check 4: 4 != null, so the comparison without swap for this subtree fails.

5. Step 5: Since the comparison without swap for the subtree failed, we now swap the children and try again:

   • Compare root1.left.left (value 4) with root2.right.right (value 4).
     • Check 5: 4 == 4, so the values match. Now, compare their children.
       • Both root1.left.left.left and root2.right.right.left are null.
       • Both root1.left.left.right and root2.right.right.right are null.
     • Since both children are null, this subtree returns true.

6. Step 6: Next, compare the right child of root1.left and left child of root2.right:

   • Both root1.left.right and root2.right.left are null.
   • Check 6: Since both children are null, this subtree returns true.

7. Step 7: Since the left and right subtrees of root1.left and root2.right match after the swap, the recursive check with swap for this subtree returns true.

8. Step 8: Now, compare the right child of root1 and left child of root2:

   • Compare root1.right (value 3) with root2.left (value 3).
   • Check 7: 3 == 3, so the values match. Now, compare their children.
     • Both root1.right.left and root2.left.left are null.
     • Both root1.right.right and root2.left.right are null.
   • Check 8: Since both children are null, this subtree returns true.

9. Final Step: Since the recursive check with swap for the left children and the comparison of the right children return true, the final result is:

   • The two trees are isomorphic, so the function returns true.

Code

// class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;

//     // Constructor for creating a new tree node
//     TreeNode(int val) {
//         this.val = val;
//         this.left = null;
//         this.right = null;
//     }
// }

class Solution {

  // Function to check if two trees are isomorphic
  public boolean isIsomorphic(TreeNode root1, TreeNode root2) {
    // If both trees are empty, they are isomorphic
    if (root1 == null && root2 == null) {
      return true;
    }

    // If one tree is empty and the other is not, they are not isomorphic
    if (root1 == null || root2 == null) {
      return false;
    }

    // If the values of current nodes do not match, trees are not isomorphic
    if (root1.val != root2.val) {
      return false;
    }

    // Check if the trees are isomorphic without swapping children
    boolean withoutSwap =
      isIsomorphic(root1.left, root2.left) &&
      isIsomorphic(root1.right, root2.right);

    // Check if the trees are isomorphic with swapped children
    boolean withSwap =
      isIsomorphic(root1.left, root2.right) &&
      isIsomorphic(root1.right, root2.left);

    // Trees are isomorphic if either case is true
    return withoutSwap || withSwap;
  }

  public static void main(String[] args) {
    // Constructing Tree 1
    TreeNode root1 = new TreeNode(1);
    root1.left = new TreeNode(2);
    root1.right = new TreeNode(3);
    root1.left.left = new TreeNode(4);

    // Constructing Tree 2
    TreeNode root2 = new TreeNode(1);
    root2.left = new TreeNode(3);
    root2.right = new TreeNode(2);
    root2.right.right = new TreeNode(4);

    // Creating an instance of Solution class
    Solution solution = new Solution();

    // Checking if the two trees are isomorphic
    boolean result = solution.isIsomorphic(root1, root2);

    // Printing the result
    System.out.println("Are the two trees isomorphic? " + result);
  }
}

Complexity Analysis

Time Complexity

• Each node of both trees is visited once. At each node, we perform a constant amount of work (comparisons and recursive calls).
• Therefore, the time complexity of the solution is , where N1 and N2 are the number of nodes in root1 and root2 respectively.
• This is because we are traversing both trees simultaneously, and the traversal will stop once we reach the end of the smaller tree.

Space Complexity

• The space complexity is determined by the depth of the recursion stack.
• In the worst case (for highly unbalanced trees), the depth of recursion could be the height of the tree, leading to space complexity, where H1 and H2 are the heights of root1 and root2, respectively.
• For balanced trees, the height is logarithmic, so the space complexity is in the best case.