Tree Isomorphism Check

Implementation

boolean isomorphic(Node a, Node b) {
  if (a == null && b == null) return true;
  if (a == null || b == null || a.val != b.val) return false;
  return (isomorphic(a.left, b.left) && isomorphic(a.right, b.right))
      || (isomorphic(a.left, b.right) && isomorphic(a.right, b.left));
}

Complexity

Worst case O(4^N) with two options per node. Memoize with (subtree_a, subtree_b) as key to reduce.

Hashing for O(N)

Assign hash per subtree based on children hashes (sorted). Two isomorphic subtrees have same hash. Great for tree canonicalization.

Related: mirror trees

Isomorphic + only exact mirror (no equal case) = symmetric variant.