Tree Isomorphism Problem - Algorithm, Visualization, and Code Examples
⬅ Previous TopicLowest Common Ancestor (LCA) in a Binary Tree
Next Topic ⮕Check if a Binary Tree Contains Duplicate Subtrees of Size 2 or More
Next Topic ⮕Check if a Binary Tree Contains Duplicate Subtrees of Size 2 or More
Solution
Algorithm Steps
Code
Python
Java
JavaScript
C
C++
C#
Kotlin
Swift
Go
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))