Tree Isomorphism Problem - Algorithm, Visualization, and Code Examples

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❯

Understanding the Problem

We are given two binary trees. The goal is to determine whether they are isomorphic. Two trees are said to be isomorphic if they have the same structure and node values, or if they can be made identical by swapping the left and right children of some nodes.

In simpler terms, two trees are isomorphic if we can transform one into the other by flipping some children at various levels, without changing any of the node values.

Step-by-Step Solution with Example

Step 1: Understand What We’re Comparing

Let’s say we have two trees:


Tree 1:           Tree 2:

     1                1
   /               /     2     3          3     2

At first glance, they look different because the children are flipped. But if we allow swapping, they become structurally identical with the same values at corresponding positions. So they are isomorphic.

Step 2: Base Case - Both Trees Are Empty

If both nodes are null, they are trivially isomorphic. Nothing to compare. Return true.

Step 3: One Node Is Null, Other Is Not

If one of the nodes is null and the other isn’t, the trees cannot be isomorphic. A tree with nodes cannot be made to match an empty tree. Return false.

Step 4: Values at the Nodes Differ

If the values stored at the current nodes are different, they can never be isomorphic, regardless of child swaps. Return false.

Step 5: Check for Isomorphism Recursively

Now comes the real check. We have two possibilities:

No Swap: Left with left and right with right.
Swap: Left with right and right with left.

We recursively check both cases. If either results in all corresponding subtrees being isomorphic, the answer is true.

Step 6: Implement the Recursive Function

boolean isIsomorphic(TreeNode n1, TreeNode n2) {
    if (n1 == null && n2 == null) return true;
    if (n1 == null || n2 == null) return false;
    if (n1.val != n2.val) return false;

    boolean noSwap = isIsomorphic(n1.left, n2.left) && isIsomorphic(n1.right, n2.right);
    boolean swap = isIsomorphic(n1.left, n2.right) && isIsomorphic(n1.right, n2.left);

    return noSwap || swap;
}

Edge Cases

Case 1: Both Trees Are Empty

This is the simplest case. Return true.

Case 2: One Tree Is Empty

Not isomorphic. Return false.

Case 3: Root Values Are Different

No possible swap can make values equal. Return false.

Case 4: Trees Are Exactly the Same

All values and positions match. No swap needed. Return true.

Case 5: Children Are Swapped

Swap makes them match. Return true.

Case 6: Multiple Swaps Needed

If recursive swaps at multiple levels result in match, still return true.

Case 7: Structure Too Different

If number of children, or their arrangement is too different, no amount of flipping helps. Return false.

Finally

Tree isomorphism is all about recursive comparison and being open to flipping children when needed. For beginners, think of it like trying to align two tangled ropes — you’re allowed to twist one, but you can’t cut or change their labels. Practice with examples and draw trees to build your intuition.

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.

Code

C++

Python

Java

Rust

Kotlin

Swift

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode* createNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = node->right = NULL;
    return node;
}

bool isIsomorphic(TreeNode* root1, TreeNode* root2) {
    if (!root1 && !root2) return true;
    if (!root1 || !root2) return false;
    if (root1->val != root2->val) return false;
    return (isIsomorphic(root1->left, root2->left) && isIsomorphic(root1->right, root2->right)) ||
           (isIsomorphic(root1->left, root2->right) && isIsomorphic(root1->right, root2->left));
}

int main() {
    TreeNode* tree1 = createNode(1);
    tree1->left = createNode(2);
    tree1->right = createNode(3);
    tree1->left->left = createNode(4);
    tree1->right->right = createNode(5);

    TreeNode* tree2 = createNode(1);
    tree2->left = createNode(3);
    tree2->right = createNode(2);
    tree2->left->left = createNode(5);
    tree2->right->right = createNode(4);

    if (isIsomorphic(tree1, tree2))
        printf("Trees are isomorphic.\n");
    else
        printf("Trees are not isomorphic.\n");

    return 0;
}

⬅ Previous TopicLowest Common Ancestor (LCA) in a Binary Tree

Next Topic ⮕Check if a Binary Tree Contains Duplicate Subtrees of Size 2 or More

Comments

Loading comments...