Tree Isomorphism Problem - Algorithm, Visualization, and Code Examples

Contents

ProblemExamplesSolutionAlgorithmCode

Problem Statement❯

Given two binary trees, determine whether they are isomorphic. Two trees are isomorphic if one can be transformed into the other by swapping the left and right children of some nodes. This is not just about structure — the node values must also match. Your task is to check if the trees can become identical by any number of such flips.

Examples❯

Tree 1 (Level Order) Tree 2 (Level Order) Isomorphic? Description
[1, 2, 3, 4, 5, 6, 7]
[1, 3, 2, 7, 6, 5, 4]
true Trees are isomorphic by swapping left and right children at nodes 1 and 2.
[1, 2, 3]
[1, 2, 4]
false Tree 2 has a different node (4 instead of 3), making them not isomorphic.
[1]
[1]
true Both trees have only a single identical node, hence are trivially isomorphic.
[] [] true Both trees are empty; empty trees are considered isomorphic.
[1, 2, null, 3]
[1, null, 2, null, 3]
true Structures differ but by flipping child nodes they become structurally identical with same values.

Solution❯

Case 1: Both Trees Are Empty

If both trees are empty (i.e., both root nodes are null), then they are trivially isomorphic. This is the base case and the simplest scenario. There’s nothing to compare, so the answer is Yes.

Case 2: One Tree Is Empty, the Other Is Not

If only one of the trees is empty, they can't be isomorphic. A non-empty structure can't match an empty one — regardless of how you flip the children. Hence, the answer is No.

Case 3: Node Values Are Different

Even if the structure matches exactly, differing node values break the isomorphism. For instance, if the left child of one root is 2 and the left child of the other is 5, there's no flipping that can resolve the mismatch. Thus, the answer is No.

Case 4: Trees Are Identical

If both trees have the same structure and the same node values, then they are naturally isomorphic. No flipping is needed. The answer is Yes.

Case 5: Trees Become Identical After Swapping

In many cases, the trees may not look the same initially, but a swap of children at certain nodes makes them identical. For example, if tree1 has left = 2 and right = 3, and tree2 has left = 3 and right = 2, a flip at the root node makes them identical. Recursion is used to check both ‘no swap’ and ‘with swap’ conditions at every node.

Case 6: Trees Require Multiple Swaps

Sometimes, the trees need multiple swaps at different levels to become isomorphic. This involves checking all combinations recursively. As long as you can match all corresponding subtrees via a series of such swaps, the trees are considered isomorphic. The answer is Yes.

Case 7: Deep Structural Differences

If the trees differ significantly in depth or structure in a way that no sequence of child swaps can fix, then they are not isomorphic. Even if the values are the same, the arrangement of nodes matters. The answer is No.

Algorithm Steps❯

  1. If both trees are empty, they are isomorphic.
  2. If one tree is empty and the other is not, they are not isomorphic.
  3. If the values of the current nodes differ, return false.
  4. 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.
  5. If either condition holds, the trees are isomorphic.

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))