Tree Isomorphism and Hashing

Two trees are isomorphic if one can be relabelled into the other while preserving adjacency: a bijection $\phi$ with $(u,v)\in E_1⟺(\phi u,\phi v)\in E_2$.

Graph isomorphism in general has no known polynomial algorithm. For trees it is solved in $O(n)$ — or $O(n\log n)$ with sorting — by canonical encoding.

AHU canonical encoding

Aho-Hopcroft-Ullman: build a canonical string for a rooted tree bottom-up.

• A leaf encodes as ().
• An internal node encodes its children, sorts their encodings lexicographically, and wraps the concatenation in brackets.

Sorting is what makes it canonical — it removes the arbitrary child ordering.

string encode(int u, int p) {
    vector<string> parts;
    for (int v : adj[u]) if (v != p) parts.push_back(encode(v, u));
    sort(parts.begin(), parts.end());
    string s = "(";
    for (auto& t : parts) s += t;
    return s + ")";
}

For unrooted trees, root each at a center first. Since there are at most two centers, compare one tree’s encoding against both of the other’s:

bool isomorphic(int n, vector<vector<int>>& t1, vector<vector<int>>& t2) {
    auto c1 = treeCenters(n, t1), c2 = treeCenters(n, t2);
    adj = t1; string e1 = encode(c1[0], -1);
    adj = t2;
    for (int c : c2) if (encode(c, -1) == e1) return true;
    return false;
}

Complexity: $O(n\log n)$ as written (string sorting); $O(n)$ with level-by-level integer relabelling, where each level’s child-id tuples are radix sorted and mapped to fresh small integers.

Tree hashing — the practical alternative

Strings get long. For most purposes, hash the canonical form instead:

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
map<vector<unsigned long long>, unsigned long long> memo;
 
unsigned long long shift(unsigned long long x) {   // scramble, avoid trivial collisions
    x += 0x9e3779b97f4a7c15ULL;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
    x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
    return x ^ (x >> 31);
}
 
unsigned long long hashTree(int u, int p) {
    vector<unsigned long long> ch;
    for (int v : adj[u]) if (v != p) ch.push_back(hashTree(v, u));
    sort(ch.begin(), ch.end());
    unsigned long long h = 1;
    for (auto c : ch) h += shift(c);              // commutative, order-independent
    return h;
}

Do not use a fixed simple hash

h = h * B + child without sorting is order-dependent and wrong. sum of child hashes without the shift scramble collides trivially (two children hashing to $a,b$ collide with $a-1,b+1$). The random shift on each child’s hash before summing is what makes collisions unlikely, and the random seed is what makes it un-hackable.

Applications

Problem	Approach
Are two trees isomorphic?	AHU or hashing at the centers
Count distinct subtree shapes	hash every subtree, count distinct values
Find all repeated subtrees	group vertices by subtree hash
Is a tree symmetric about a vertex?	compare children’s hashes for duplicates
Canonical form for memoisation	hash as a DP key over tree shapes
Count non-isomorphic trees on $n$ vertices	DP over canonical forms

Counting distinct subtrees is the most common contest use, and hashing makes it a five-line addition to any DFS.

Rooted vs unrooted

• Rooted isomorphism — compare encodings directly.
• Unrooted isomorphism — root at the center(s) first. Rooting at an arbitrary vertex is wrong: two isomorphic trees rooted differently produce different encodings.

Beyond trees

Graph isomorphism for general graphs is in quasipolynomial time (Babai, 2016) and is not known to be in P or NP-complete. In practice, nauty and similar tools use refinement plus backtracking. For contest purposes: if a problem asks about isomorphism, the graph is almost certainly a tree or has bounded structure.

See also: Tree Center · String Hashing · Tree Fundamentals