Check if Two Trees are Isomorphic

Easy
1894.

Check if Two Trees are Isomorphic

EasyTreeDepth-First SearchRecursionAmazonMicrosoft

Check if Two Trees are Isomorphic is an easy coding problem on depth-first search, trees and recursion, asked in Amazon and Microsoft interviews.

Two binary trees are isomorphic if one can be turned into the other by swapping the left and right children of any number of its nodes (possibly none). Node values must match too: a node can only correspond to a node holding the same value.

Given the roots root1 and root2 of two binary trees, return true if they are isomorphic, and false otherwise.

Example 1

Input
root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5,null,null,null,null,8,7]
Output
true
Explanation
Swap the children of 1, of 3 and of 5 in the first tree and it becomes the second.

Example 2

Input
root1 = [1,2,3,4], root2 = [1,3,2,4]
Output
false
Explanation
In the first tree 4 hangs below 2; in the second it hangs below 3. No swaps move a node to a different parent.

Example 3

Input
root1 = [1,2], root2 = [1,null,2]
Output
true
Explanation
Swapping the root's children turns one into the other.

Constraints

  • 1 <= number of nodes in each tree <= 10^5
  • 1 <= Node.val <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root1
 * @param {TreeNode} root2
 * @return {boolean}
 */
var isIsomorphic = function(root1, root2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in
AI InterviewGet started

Check if Two Trees are Isomorphic — Problem & Solution

Check if Two Trees are Isomorphic solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Check if Two Trees are Isomorphic is an easy coding problem on depth-first search, trees and recursion, asked in Amazon and Microsoft interviews.

Problem statement

Two binary trees are isomorphic if one can be turned into the other by swapping the left and right children of any number of its nodes (possibly none). Node values must match too: a node can only correspond to a node holding the same value.

Given the roots root1 and root2 of two binary trees, return true if they are isomorphic, and false otherwise.

Example 1

Input: root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5,null,null,null,null,8,7]
Output: true
Explanation: Swap the children of 1, of 3 and of 5 in the first tree and it becomes the second.

Example 2

Input: root1 = [1,2,3,4], root2 = [1,3,2,4]
Output: false
Explanation: In the first tree 4 hangs below 2; in the second it hangs below 3. No swaps move a node to a different parent.

Example 3

Input: root1 = [1,2], root2 = [1,null,2]
Output: true
Explanation: Swapping the root's children turns one into the other.

Constraints

  • 1 <= number of nodes in each tree <= 10^5
  • 1 <= Node.val <= 10^5

Hints for Check if Two Trees are Isomorphic

  1. Hint 1

    Matching roots must hold the same value; after that the question repeats for their children.

  2. Hint 2

    The children can be matched straight (left with left, right with right) or crossed (left with right) — at each node, either is allowed.

  3. Hint 3

    Write iso(a, b): both null → true, one null or different values → false, otherwise straight-match or cross-match the children recursively.

How to solve Check if Two Trees are Isomorphic

Swaps at different nodes are independent, so two trees are isomorphic exactly when their roots agree and their pairs of subtrees are isomorphic either in the same order or in the crossed order.

Approach

  1. If both nodes are null, return true; if exactly one is null, return false.
  2. If their values differ, return false.
  3. Return (iso(a.left, b.left) and iso(a.right, b.right)) or (iso(a.left, b.right) and iso(a.right, b.left)).

Why it works

A sequence of swaps either swaps the root's children or does not; the remaining swaps act inside the subtrees. So the root pair matches if and only if one of the two pairings of the subtrees matches, which is exactly the recursion.

Complexity

  • Time — O(n) in typical trees (each pair of nodes is compared a bounded number of times); O(n²) in adversarial cases where the straight match fails late
  • Space — O(h) for the recursion

Pitfalls

  • Comparing only the multiset of values per level is not enough — parents must match too.
  • Short-circuit evaluation keeps the crossed check from running when the straight one already succeeds.

Reference solution

Python

from typing import Optional

def isIsomorphic(root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
    if root1 is None and root2 is None:
        return True
    if root1 is None or root2 is None or 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))

Java

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

C++

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

JavaScript

var isIsomorphic = function(root1, root2) {
    if (root1 === null && root2 === null) return true;
    if (root1 === null || root2 === null || 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));
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals