Chapter 11 · Advanced Tree Algorithms
Tree Hashing and Isomorphism
A canonical form for unordered rooted trees, a randomised hash that is one line, and the collision you must not ignore.
Two rooted trees are isomorphic if a bijection between vertices preserves the root and adjacency. Unrooted: they become isomorphic after rooting at their respective centers (Centroid Decomposition gives the center(s)).
Define φ(v) = "(" + sort({φ(c) : c child of v}) + ")". Then φ(u) = φ(v) as strings iff the rooted subtrees at u and v are isomorphic. Comparing subtrees is thus reduced to comparing hashes of φ, and the tree isomorphism class is φ(root).
Induction on height. Two children multisets are equal (as isomorphism classes) iff their sorted φ sequences are equal, since φ is by the induction hypothesis a complete invariant for the children. The parenthesis wrapper makes the encoding prefix-free, so concatenation cannot create ambiguity, and the sort kills the arbitrary order of children. Hence equality of strings ⟺ equality of unordered child-class multisets ⟺ isomorphism. ∎
// AHU-style canonical labelling in O(n log n) without strings:
// level the tree by height, then map each vertex's sorted child-label list to a fresh id.
vector<int> hgt(n), lab(n);
{
vector<vector<int>> by_height(n + 1);
function<void(int,int)> dfs = [&](int v, int p) {
for (int to : g[v]) if (to != p) { dfs(to, v); hgt[v] = max(hgt[v], hgt[to] + 1); }
by_height[hgt[v]].push_back(v);
};
dfs(root, -1);
map<vector<int>, int> ids; int nxt = 0;
for (int h = 0; h <= n; h++) {
for (int v : by_height[h]) {
vector<int> kids;
for (int to : g[v]) if (to != par[v]) kids.push_back(lab[to]);
sort(kids.begin(), kids.end());
auto [it, ok] = ids.try_emplace(kids, nxt);
if (ok) nxt++;
lab[v] = it->second;
}
}
}
// two rooted trees are isomorphic iff their roots get the same label id (run both through one map)with P a random-looking polynomial (e.g. P(x) = x · A + B mod M, A,B random 64-bit) and M = 261-1, using unsigned long long with a Mersenne reduction (Linear Recurrences from Graphs and Matrices). The sum is order-insensitive, which is exactly what unordered children need. Same class: xor instead of sum (careful: xor of equal child hashes cancels — a star with two identical leaves hashes the same as the bare center, a real bug).
- A sum of random hashes mod 264 has collision probability per pair ≈ 2-64 only if the child hashes are independent — an adversary who knows your constants can construct collisions. Seed the bases at runtime (
chrono::steady_clock) rather than hard-coding them (Trie (Prefix Tree) and Its Relatives). - Two-tree comparison by maximum matching of children: with hashing you get it for free, but "the trees are isomorphic" statements should be double-hashed with two moduli, or verified by an explicit canonical form when n ≤ 106 (the O(nlog n) version above is deterministic and exact).
- Weighted/labelled variants: include the label in the hash before the polynomial, i.e. hash(v) = P(label[v], ∑c hash(c)), otherwise relabellings collide.
Unrooted trees and forests
- Unrooted: compute φ at both centers (Centroid Decomposition has at most two) and take the minimum/sum of the two — the canonical form of an unrooted tree is "(" + min(φ(c1), φ(c2)) ")" appropriately;
- Rooted at every vertex: "for which roots is the tree isomorphic to a given pattern" — reroot the hash in O(n log n) total with φall(v) = P(all neighbour hashes) (subtree + complement hashes);
- Counting non-isomorphic trees on n vertices: the generating-function (Pólya/Otter) route, not hashing — the sequence is OEIS A000055;
- Tree isomorphism as a graph isomorphism special case: linear time deterministic (Hopcroft–Wong for bounded degree, or the AHU algorithm above) — unlike general GI, which is why this is contest-solvable.