Solve the Tree Isomorphism Problem

Algorithm Steps

If both trees are empty, they are isomorphic.
If one tree is empty and the other is not, they are not isomorphic.
If the values of the current nodes differ, return false.
Recursively check two possibilities: (a) the left subtree of tree1 is isomorphic to the left subtree of tree2 and the right subtree of tree1 is isomorphic to the right subtree of tree2, OR (b) the left subtree of tree1 is isomorphic to the right subtree of tree2 and the right subtree of tree1 is isomorphic to the left subtree of tree2.
If either condition holds, the trees are isomorphic.

Tree Isomorphism Problem - Code Examples Code

Python

Java

JavaScript

C++

Kotlin

Swift

Php

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def isIsomorphic(root1, root2):
    if not root1 and not root2:
        return True
    if not root1 or not root2:
        return False
    if root1.val != root2.val:
        return False
    return (isIsomorphic(root1.left, root2.left) and isIsomorphic(root1.right, root2.right)) or \
           (isIsomorphic(root1.left, root2.right) and isIsomorphic(root1.right, root2.left))

# Example usage:
if __name__ == '__main__':
    # Construct two example trees
    # Tree 1:       1
    #             /   \
    #            2     3
    #           /       \
    #          4         5
    
    # Tree 2:       1
    #             /   \
    #            3     2
    #           /       \
    #          5         4
    
    tree1 = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3, None, TreeNode(5)))
    tree2 = TreeNode(1, TreeNode(3, TreeNode(5)), TreeNode(2, None, TreeNode(4)))
    print(isIsomorphic(tree1, tree2))