Tree Isomorphism Check, in depth: AHU canonical ids, centres for free trees and subtree hashing

Four questions that share a name

Be precise about which question you are answering, because there are four and they have different algorithms.

• Rooted, unordered. Each tree has a root and child order does not matter, as in an organisation chart or a JSON object. This is the core AHU case.
• Rooted, ordered. Child order matters, as in a syntax tree where subtraction operands cannot be swapped. A synchronised traversal of both trees decides it.
• Unrooted (free) trees. Only an undirected acyclic connected graph. You must pick a root both trees agree on, which the centre provides.
• Labelled variants. Node labels (an operator, an atom) must match as well as shape. AHU absorbs them by putting the label in the key.

Cheap necessary conditions exist: equal node counts, depths and degree multisets. None is sufficient; two seven-node trees can share every degree and still differ. You need a canonical form: a value that two trees share exactly when they are isomorphic.

Why the obvious approaches fail

Brute force tries every bijection between the node sets, n! of them, so it dies before n reaches fifteen. It is still worth writing as a test oracle for small trees; the code below was checked that way.

The textbook improvement is a canonical string: a leaf is (), and an internal node is a parenthesis around its children's strings sorted lexicographically. Equal root strings mean isomorphic trees. It is correct but not linear: each string is as long as its subtree, so on a path the strings total about n squared over two characters. AHU's fix is to carry small integers upward instead of whole strings.

The AHU algorithm: name every subtree shape

The AHU insight: you only need to know which subtrees are equal, not what they look like. Give every distinct subtree shape a small integer name, and describe each node by the sorted list of its children's names, working bottom-up.

1. Root the tree and compute an order in which every child precedes its parent. Reversed breadth-first order works without recursion.
2. Each leaf has the empty tuple as key. Look it up in a dictionary shared by both trees, assigning the next integer if new. All leaves get id 0.
3. For each internal node, sort its children's ids into a tuple and look that up in the same dictionary, assigning a fresh integer when unseen.
4. The rooted trees are isomorphic exactly when their roots get the same id.

Correctness follows by induction on height: equal ids mean equal multisets of child ids, which by hypothesis mean isomorphic child subtrees that can be matched pairwise. The shared dictionary is essential; with separate tables, id 3 in one tree could mean a different shape in the other.

Child lists partition the n minus 1 edges, so hashing is linear overall and sorting is O(n log n) at worst. The original presentation reaches strict O(n) by processing level by level with radix sort; the comparison-sort version is simpler and fast enough in practice.

Worked example by hand

Tree A is rooted at a with children b and c; b has leaf children d and e; c is a leaf. Tree B is rooted at x with children y and z; y is a leaf; z has leaf children u and w. B is A mirrored. Run AHU with one empty shared table.

1. Leaves d, e, c, y, u and w have the empty key: the table gets () -> 0 and all get id 0.
2. Node b has key (0, 0), which is new: (0, 0) -> 1. Node z has the same key and reuses id 1.
3. Root a has children with ids 1 and 0; sorted, the key (0, 1) becomes id 2. Root x has children 0 and 1, the same sorted key, so x gets id 2.
4. Equal root ids: the trees are isomorphic. The sort made the mirroring irrelevant.

Compare A with a five-node star, a root with four leaf children. Sizes match, but the root key (0, 0, 0, 0) gets a fresh id and AHU reports a mismatch.

To recover the mapping, walk both trees top-down: at each matched pair, group children by id and pair them off within each group. Equal ids guarantee equal group sizes, so this is linear once ids are known.

Tested iterative implementation

Trees are adjacency lists with nodes numbered from zero. The code is iterative because recursion overflows Python's default limit of about a thousand frames on a long chain. It was tested against the permutation oracle on thousands of random tree pairs of up to seven nodes, rooted and unrooted, and on a one-million-node path.

from collections import deque


def centers(adj):
    """Return the one or two centres of a tree given as an adjacency list."""
    n = len(adj)
    if n == 1:
        return [0]
    deg = [len(a) for a in adj]
    leaves = deque(i for i in range(n) if deg[i] == 1)
    remaining = n
    while remaining > 2:                 # peel one layer of leaves per round
        for _ in range(len(leaves)):
            u = leaves.popleft()
            remaining -= 1
            for v in adj[u]:
                deg[v] -= 1
                if deg[v] == 1:
                    leaves.append(v)
    return list(leaves)


def ahu_id(adj, root, table):
    """AHU canonical id of the tree rooted at root. Iterative: no recursion limit."""
    parent = {root: None}
    order = [root]
    for u in order:                      # BFS: every parent precedes its children
        for v in adj[u]:
            if v not in parent:
                parent[v] = u
                order.append(v)
    kids = {u: [] for u in order}
    cid = {}
    for u in reversed(order):            # every child precedes its parent
        key = tuple(sorted(kids[u]))     # unordered tree: sort the multiset
        cid[u] = table.setdefault(key, len(table))
        if parent[u] is not None:
            kids[parent[u]].append(cid[u])
    return cid[root]


def rooted_isomorphic(adj1, r1, adj2, r2):
    if len(adj1) != len(adj2):
        return False
    table = {}                           # ONE table, so ids are comparable
    return ahu_id(adj1, r1, table) == ahu_id(adj2, r2, table)


def isomorphic(adj1, adj2):
    """Unrooted tree isomorphism: root both trees at their centres."""
    if len(adj1) != len(adj2):
        return False
    c1, c2 = centers(adj1), centers(adj2)
    if len(c1) != len(c2):
        return False
    table = {}
    target = ahu_id(adj1, c1[0], table)
    return any(ahu_id(adj2, c, table) == target for c in c2)

The table is passed in, so calls within one comparison share it. Because ids are dense integers, one table can serve a whole collection: to bucket a million small trees by shape, compute each root id and group by it, one linear pass instead of quadratic pairwise checks.

Unrooted trees: root at the centre

Free trees need a root that any isomorphism preserves: the centre. Repeatedly delete all current leaves; the last one or two vertices standing are the centres. An isomorphism maps leaves to leaves, hence each peeling round to its counterpart, hence centres to centres. Every tree has one centre or two adjacent ones:

• Different numbers of centres: not isomorphic.
• One centre each: root both there and compare.
• Two each: root the first tree at either centre and compare against the second rooted at each of its centres; one pairing matches if any isomorphism exists. One table serves all calls.

A four-node path has two centres; a star has one. Centre finding is linear, so unrooted isomorphism costs the same as rooted.

Hashing instead of a table, and collision risk

Many systems skip the shared table and hash instead: a leaf hashes to a constant, an internal node to a hash of its children's sorted hashes, Merkle-style. Hashes are computed per tree, so they work across processes and time; you can index them in a database and compare a new tree against last year's without a giant in-memory table. It is the structure a Merkle tree uses for integrity.

The price: equal hashes no longer prove isomorphism. With 64 bits a false match between two given trees is very unlikely, but across a billion trees the birthday bound makes one plausible. Treat a hash match as a candidate and confirm with AHU, or use 128 bits. Never combine children by summing or XOR-ing: sums collide for many multisets and XOR cancels identical children. Hash the sorted sequence as a whole, as you would any hash table key, and seed it against adversarial input.

Variants you will meet

• Labelled nodes. Put the label first in the key: (label, tuple(sorted(child_ids))). A plus node with children x and y and a times node with the same children then get different ids.
• Ordered trees. Use tuple(child_ids) without sorting. Sorting would wrongly equate a - b with b - a. An AST comparison is usually ordered for most node types and unordered for a few commutative ones; choose per node.
• Distinct subtrees in one tree. Run AHU once with one table; the number of distinct ids among all nodes is the number of distinct subtree shapes. This is how compilers find common subexpressions and how you count repeated substructures.
• Forests. Add a virtual root whose children are the forest's roots, then compare as rooted trees.
• Subtree isomorphism (is a small tree a subgraph of a large one) is a different and harder problem. It is polynomial for trees but needs bipartite matching at each node, so do not expect a hashing trick to solve it.

Failure modes

• Separate tables per tree. The most common bug. Each tree's ids are self-consistent but meaningless across trees, so the comparison is random. Pass one table, or use a deterministic hash.
• Recursion depth. Recursive AHU passes every unit test on balanced trees and crashes in production on a degenerate chain. Use the iterative order shown above.
• Comparing at the wrong root. Running the rooted algorithm on free trees, rooted at whatever node happened to be listed first, reports false negatives. Root at centres.
• Sorting where order matters, or not sorting where it does not. Decide from the semantics of the data, not from what the code you copied did.
• Memory for huge collections. A shared table grows with the number of distinct shapes. When comparing streams of trees indefinitely, switch to hashes and verify matches, or evict the table periodically.
• Graphs that are not trees. Validate the input has n minus 1 edges and is connected. Run on a graph with a cycle and the breadth-first order silently ignores the extra edge.

Trade-offs

The pattern generalises. Rooted unordered trees need sorting somewhere, because children form a multiset, and canonical ids make that sorting cheap. When you need persistence, trade exactness for hashes and add a verification step. Basic traversal mechanics are covered in BFS and DFS, and the ordered, mirror-image version of this problem appears in symmetric tree check.

What to do next

1. Decide which variant you have: rooted or free, ordered or unordered, labelled or not. Write it down next to the function.
2. Implement the iterative AHU above with one shared table, and a brute-force permutation oracle for trees of up to seven nodes.
3. Fuzz both against each other on thousands of random pairs, including single-node trees, paths and stars.
4. Run it on a one-million-node chain to prove you have no recursion limit.
5. If you need cross-process comparison, add a 64- or 128-bit subtree hash, keep AHU as the verifier and log any hash match that fails verification.
6. For deduplication jobs, compute root ids against one table and group, rather than comparing pairs.
7. Read building a tree from traversals to see when two traversals identify a tree uniquely, which is the ordered counterpart of a canonical form.