ProgramGuru

Tree Isomorphism Problem

Problem and examples

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

How it works

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.

  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.

Implementation and efficiency

C implementation

#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;
}

C++ implementation

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

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 = new TreeNode(1);
    tree1->left = new TreeNode(2);
    tree1->right = new TreeNode(3);
    tree1->left->left = new TreeNode(4);
    tree1->right->right = new TreeNode(5);

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

    if (isIsomorphic(tree1, tree2))
        cout << "Trees are isomorphic." << endl;
    else
        cout << "Trees are not isomorphic." << endl;

    return 0;
}

Python implementation

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

def is_isomorphic(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 (is_isomorphic(root1.left, root2.left) and is_isomorphic(root1.right, root2.right)) or \
           (is_isomorphic(root1.left, root2.right) and is_isomorphic(root1.right, root2.left))

if __name__ == "__main__":
    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("Trees are isomorphic." if is_isomorphic(tree1, tree2) else "Trees are not isomorphic.")

Java implementation

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) {
        val = x;
    }
}

public class TreeIsomorphism {
    public static boolean isIsomorphic(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) return true;
        if (root1 == null || root2 == null) 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));
    }

    public static void main(String[] args) {
        TreeNode tree1 = new TreeNode(1);
        tree1.left = new TreeNode(2);
        tree1.right = new TreeNode(3);
        tree1.left.left = new TreeNode(4);
        tree1.right.right = new TreeNode(5);

        TreeNode tree2 = new TreeNode(1);
        tree2.left = new TreeNode(3);
        tree2.right = new TreeNode(2);
        tree2.left.left = new TreeNode(5);
        tree2.right.right = new TreeNode(4);

        System.out.println(isIsomorphic(tree1, tree2) ? "Trees are isomorphic." : "Trees are not isomorphic.");
    }
}

JavaScript implementation

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function isIsomorphic(root1, 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));
}

const tree1 = new TreeNode(1, new TreeNode(2, new TreeNode(4)), new TreeNode(3, null, new TreeNode(5)));
const tree2 = new TreeNode(1, new TreeNode(3, new TreeNode(5)), new TreeNode(2, null, new TreeNode(4)));

console.log(isIsomorphic(tree1, tree2) ? "Trees are isomorphic." : "Trees are not isomorphic.");

Go implementation

package main

import (
    "fmt"
)

type TreeNode struct {
    val   int
    left  *TreeNode
    right *TreeNode
}

func isIsomorphic(root1, root2 *TreeNode) bool {
    if root1 == nil && root2 == nil {
        return true
    }
    if root1 == nil || root2 == nil {
        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))
}

func main() {
    tree1 := &TreeNode{1, &TreeNode{2, &TreeNode{4, nil, nil}, nil}, &TreeNode{3, nil, &TreeNode{5, nil, nil}}}
    tree2 := &TreeNode{1, &TreeNode{3, &TreeNode{5, nil, nil}, nil}, &TreeNode{2, nil, &TreeNode{4, nil, nil}}}

    if isIsomorphic(tree1, tree2) {
        fmt.Println("Trees are isomorphic.")
    } else {
        fmt.Println("Trees are not isomorphic.")
    }
}

Rust implementation

struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}

fn is_isomorphic(root1: &Option<Box<TreeNode>>, root2: &Option<Box<TreeNode>>) -> bool {
    match (root1, root2) {
        (None, None) => true,
        (Some(_), None) | (None, Some(_)) => false,
        (Some(n1), Some(n2)) => {
            n1.val == n2.val &&
            ((is_isomorphic(&n1.left, &n2.left) && is_isomorphic(&n1.right, &n2.right)) ||
             (is_isomorphic(&n1.left, &n2.right) && is_isomorphic(&n1.right, &n2.left)))
        }
    }
}

fn main() {
    let tree1 = Some(Box::new(TreeNode {
        val: 1,
        left: Some(Box::new(TreeNode {
            val: 2,
            left: Some(Box::new(TreeNode { val: 4, left: None, right: None })),
            right: None,
        })),
        right: Some(Box::new(TreeNode {
            val: 3,
            left: None,
            right: Some(Box::new(TreeNode { val: 5, left: None, right: None })),
        })),
    }));

    let tree2 = Some(Box::new(TreeNode {
        val: 1,
        left: Some(Box::new(TreeNode {
            val: 3,
            left: Some(Box::new(TreeNode { val: 5, left: None, right: None })),
            right: None,
        })),
        right: Some(Box::new(TreeNode {
            val: 2,
            left: None,
            right: Some(Box::new(TreeNode { val: 4, left: None, right: None })),
        })),
    }));

    println!("{}", if is_isomorphic(&tree1, &tree2) { "Trees are isomorphic." } else { "Trees are not isomorphic." });
}

Kotlin implementation

class TreeNode(val value: Int, var left: TreeNode? = null, var right: TreeNode? = null)

fun isIsomorphic(root1: TreeNode?, root2: TreeNode?): Boolean {
    if (root1 == null && root2 == null) return true
    if (root1 == null || root2 == null) return false
    if (root1.value != root2.value) return false
    return (isIsomorphic(root1.left, root2.left) && isIsomorphic(root1.right, root2.right)) ||
           (isIsomorphic(root1.left, root2.right) && isIsomorphic(root1.right, root2.left))
}

fun main() {
    val tree1 = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3, null, TreeNode(5)))
    val tree2 = TreeNode(1, TreeNode(3, TreeNode(5)), TreeNode(2, null, TreeNode(4)))

    println(if (isIsomorphic(tree1, tree2)) "Trees are isomorphic." else "Trees are not isomorphic.")
}

Swift implementation

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?
    init(_ val: Int, _ left: TreeNode? = nil, _ right: TreeNode? = nil) {
        self.val = val
        self.left = left
        self.right = right
    }
}

func isIsomorphic(_ root1: TreeNode?, _ root2: TreeNode?) -> Bool {
    if root1 == nil && root2 == nil { return true }
    if root1 == nil || root2 == nil { 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))
}

let tree1 = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3, nil, TreeNode(5)))
let tree2 = TreeNode(1, TreeNode(3, TreeNode(5)), TreeNode(2, nil, TreeNode(4)))

print(isIsomorphic(tree1, tree2) ? "Trees are isomorphic." : "Trees are not isomorphic.")

TypeScript implementation

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function isIsomorphic(root1: TreeNode | null, root2: TreeNode | null): boolean {
    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));
}

const tree1 = new TreeNode(1, new TreeNode(2, new TreeNode(4)), new TreeNode(3, null, new TreeNode(5)));
const tree2 = new TreeNode(1, new TreeNode(3, new TreeNode(5)), new TreeNode(2, null, new TreeNode(4)));

console.log(isIsomorphic(tree1, tree2) ? "Trees are isomorphic." : "Trees are not isomorphic.");