Pattern Guide
Tree Isomorphism & Canonical Forms
"Two trees are isomorphic iff they have the same canonical form. AHU in O(n log n)."
Two rooted trees are isomorphic if one can be transformed to the other by relabeling nodes. The canonical form assigns each subtree a unique label based on its structure. AHU (Aho, Hopcroft, Ullman) algorithm: sort children's canonical forms, recursively assign labels. Two trees are isomorphic iff their roots have the same canonical label. For unrooted trees: check from both centers.
Problems you can solve with this pattern
4 problems · click any to start solving
function treeCanonical(n, edges, root = 0) {
const adj = Array.from({length: n}, () => []);
for (const [u, v] of edges) { adj[u].push(v); adj[v].push(u); }
function canonical(u, parent) {
const childLabels = [];
for (const v of adj[u]) {
if (v !== parent) childLabels.push(canonical(v, u));
}
childLabels.sort(); // sort for canonical order
return '(' + childLabels.join('') + ')';
}
return canonical(root, -1);
}
function areIsomorphic(n1, edges1, n2, edges2) {
if (n1 !== n2) return false;
// Find centers of each tree
const findCenters = (n, edges) => {
const adj = Array.from({length: n}, () => []);
const deg = new Array(n).fill(0);
for (const [u, v] of edges) { adj[u].push(v); adj[v].push(u); deg[u]++; deg[v]++; }
let leaves = deg.map((d, i) => d <= 1 ? i : -1).filter(i => i >= 0);
let remaining = n;
while (remaining > 2) {
remaining -= leaves.length;
const next = [];
for (const l of leaves) for (const v of adj[l]) if (--deg[v] === 1) next.push(v);
leaves = next;
}
return leaves;
};
const c1 = findCenters(n1, edges1), c2 = findCenters(n2, edges2);
if (c1.length !== c2.length) return false;
const forms1 = c1.map(c => treeCanonical(n1, edges1, c)).sort();
const forms2 = c2.map(c => treeCanonical(n2, edges2, c)).sort();
return forms1.every((f, i) => f === forms2[i]);
}Canonical form of a rooted tree: leaf = "()". Internal node = "(" + sorted concatenation of children's canonical forms + ")". Two rooted trees are isomorphic iff they have the same canonical string. For unrooted trees: find the center(s) of each tree (at most 2), root at center, compare canonical forms. O(n log n) to sort children's labels at each node.
function treeCanonical(n, edges, root = 0) {
const adj = Array.from({length: n}, () => []);
for (const [u, v] of edges) { adj[u].push(v); adj[v].push(u); }
function canonical(u, parent) {
const childLabels = [];
for (const v of adj[u]) {
if (v !== parent) childLabels.push(canonical(v, u));
}
childLabels.sort(); // sort for canonical order
return '(' + childLabels.join('') + ')';
}
return canonical(root, -1);
}
function areIsomorphic(n1, edges1, n2, edges2) {
if (n1 !== n2) return false;
// Find centers of each tree
const findCenters = (n, edges) => {
const adj = Array.from({length: n}, () => []);
const deg = new Array(n).fill(0);
for (const [u, v] of edges) { adj[u].push(v); adj[v].push(u); deg[u]++; deg[v]++; }
let leaves = deg.map((d, i) => d <= 1 ? i : -1).filter(i => i >= 0);
let remaining = n;
while (remaining > 2) {
remaining -= leaves.length;
const next = [];
for (const l of leaves) for (const v of adj[l]) if (--deg[v] === 1) next.push(v);
leaves = next;
}
return leaves;
};
const c1 = findCenters(n1, edges1), c2 = findCenters(n2, edges2);
if (c1.length !== c2.length) return false;
const forms1 = c1.map(c => treeCanonical(n1, edges1, c)).sort();
const forms2 = c2.map(c => treeCanonical(n2, edges2, c)).sort();
return forms1.every((f, i) => f === forms2[i]);
}- Canonical string: "()" for leaf, "(sorted children forms)" for internal
- Hashing: assign integer hash to each canonical form
- AHU algorithm: O(n log n) using sort + relabeling
For unrooted trees:
1. Find center (1 or 2 nodes)
2. Root at center
3. Compare canonical forms
Applications:
- Chemical structure comparison
- Parse tree equivalence
- Network topology matching
- Phylogenetic tree comparison
Subtree isomorphism: Find if T₁ is isomorphic to any subtree of T₂. O(n₁ × n₂) brute force, O(n₁ × n₂ / log n) with hashing.