Tree Algorithms

Tree Isomorphism

What is Tree Isomorphism?

Two binary trees are isomorphic if one can be transformed into the other by swapping the left and right children at any number of nodes — the values and the overall branching structure must match, but the left/right arrangement at each node is allowed to flip. It's a looser notion of "the same tree" than exact structural equality: two trees that look like mirror images of each other in places can still be isomorphic.

How Does It Work?

The check is a recursive comparison of two nodes at a time, starting from both roots. If both are empty, they match. If exactly one is empty, or their values differ, the trees aren't isomorphic. Otherwise, the node's children are compared two ways: "straight" (left-with-left, right-with-right) and "flipped" (left-with-right, right-with-left). If either pairing matches all the way down, the current pair of nodes is isomorphic.

This differs from an exact structural-equality check only in that extra flipped attempt — without it, this is the same algorithm used to test whether two trees are identical. The flip is what makes isomorphism forgiving of left/right orientation while still being strict about values and shape.

Tree B is Tree A with children swapped at nodes 1 and 3 — they're isomorphic
123451b3b2b5b4b≅
Children swapped

Algorithm Steps

  1. If both nodes are null, they match
  2. If exactly one is null, or their values differ, the trees are not isomorphic — stop
  3. Otherwise, compare children two ways:
    • Straight: left-with-left and right-with-right
    • Flipped: left-with-right and right-with-left
  4. If either pairing matches recursively, the current nodes are isomorphic

Time Complexity

  • Time Complexity: O(n) in the best case, up to O(4^n) in the worst case for the naive version — in practice close to O(n) for most trees since a mismatch usually short-circuits early.
  • Space Complexity: O(h) — recursion stack depth equals the smaller tree's height.

Time Complexity Analysis

Advertisement

Isomorphism checks are common wherever "same shape regardless of arbitrary left/right layout choices" matters: comparing parse trees or expression trees generated by different tools, verifying that a serialized tree round-trips correctly regardless of child ordering, and canonicalizing tree-shaped data before hashing or deduplication.

Daily DSA Challenge by Scale Engineer

Check whether two trees are isomorphic — identical in structure once children can be freely swapped

Build two trees to compare
Tree A
No tree built yet
Tree B
No tree built yet
Internal nodeLeaf nodeRootMatched pairChildren swappedMismatch

Test Your Knowledge before moving forward!

Tree Isomorphism Quiz

How it works:

  • +1 point for each correct answer
  • 0 points for wrong answers
  • -0.5 point penalty for viewing explanations
  • Earn stars based on your final score (max 5 stars)

Tree Isomorphism Implementation

// Binary tree node
class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

// Two trees are isomorphic if one can be turned into the other by swapping
// left/right children at any number of nodes.
function isIsomorphic(a, b) {
  if (a === null && b === null) return true;
  if (a === null || b === null) return false;
  if (a.value !== b.value) return false;

  // Try children in their original order, or swapped
  const straight = isIsomorphic(a.left, b.left) && isIsomorphic(a.right, b.right);
  const flipped = isIsomorphic(a.left, b.right) && isIsomorphic(a.right, b.left);

  return straight || flipped;
}

// Usage example
// Tree A: 1(2(4,5), 3)
// Tree B: 1(3, 2(5,4))  -- same as A with children swapped at nodes 1 and 2
isIsomorphic(treeA, treeB); // true

Done With the Learning

Mark Tree Isomorphism as done and view it on your dashboard

Explore Other Tree Topics

Tree Diameter

Lowest Common Ancestor

Serialize/Deserialize

BST Insertion

In-order Traversal

Structure & Properties