---
title: "Tree Hashing and Isomorphism"
summary: A canonical form for unordered rooted trees, a randomised hash that is one line, and the collision you must not ignore.
difficulty: hard
tags: [hashing, trees, isomorphism]
time: n log n
space: n
prereq: [trees/properties, structures/trie]
see: [trees/counting, structures/trie]
---

:::definition label="Rooted isomorphism"
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 (@advanced-tree/centroid gives the center(s)).
:::

:::theorem title="Canonical form, bottom-up"
Define $\phi(v) = \texttt{"("} + \operatorname{sort}(\{\phi(c) : c \text{ child of } v\}) + \texttt{")"}$. Then $\phi(u) = \phi(v)$ as strings iff the rooted subtrees at $u$ and $v$ are isomorphic. Comparing subtrees is thus reduced to comparing hashes of $\phi$, and the tree isomorphism class is $\phi(\text{root})$.
:::

:::proof
Induction on height. Two children multisets are equal (as isomorphism classes) iff their sorted $\phi$ sequences are equal, since $\phi$ 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. ∎
:::

```cpp tree-hash.cpp
// 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)
```

:::note title="The 6-line randomised version"
$$\operatorname{hash}(v) = 1 + \sum_{c \text{ child}} \big(P(\operatorname{hash}(c)) \bmod M\big)$$
with $P$ a random-looking polynomial (e.g. $P(x) = x \cdot A + B \bmod M$, $A,B$ random 64-bit) and $M = 2^{61}-1$, using `unsigned long long` with a Mersenne reduction (@matrices/recurrences). 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).
:::

:::warning title="Collisions are not a rounding error"
- A **sum of random hashes mod $2^{64}$** has collision probability per pair $\approx 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 (@structures/trie).
- 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 \le 10^6$ (the $O(n\log n)$ version above is deterministic and exact).
- Weighted/labelled variants: include the label in the hash **before** the polynomial, i.e. $\operatorname{hash}(v) = P(\operatorname{label}[v], \sum_c \operatorname{hash}(c))$, otherwise relabellings collide.
:::

:::props title="Unrooted trees and forests"
- **Unrooted**: compute $\phi$ at both centers (@advanced-tree/centroid has at most two) and take the minimum/sum of the two — the canonical form of an unrooted tree is $\texttt{"("} + \min(\phi(c_1), \phi(c_2)) \texttt{")"}$ 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 $\phi_{\text{all}}(v) = P(\text{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.
:::

:::problems
- [[CSES 1700]] Tree Isomorphism I | https://cses.fi/problemset/task/1700 | core | rooted, canonical hash
- [[CSES 1701]] Tree Isomorphism II | https://cses.fi/problemset/task/1701 | hard | unrooted — center-based reduction
- [[CSES 1674]] Subordinates | https://cses.fi/problemset/task/1674 | easy | the subtree-shape information hashing builds on
:::