Tree Isomorphism

Two trees are isomorphic when their vertices can be put into a one-to-one correspondence preserving adjacency. Vertex labels and drawing positions do not matter. Equal vertex and degree counts are necessary but insufficient: different branching arrangements can share those statistics. We will test exact isomorphism of unrooted, unordered, unlabeled trees using rooted canonical subtree signatures and tree centers. The implementation uses deterministic signature interning rather than randomized hashes, so there is no probability of a collision.

Prerequisites: Rooted trees, postorder traversal, tree centers, sorting, and maps with vector keys.

Build the idea

1. 1. Solve the rooted version first. A leaf has an empty list of child signatures. For any other vertex, collect all child signatures and sort them, because the adjacency-list order has no structural meaning. Two rooted subtrees have the same shape exactly when their sorted child-signature lists match. In a conceptual bracket representation, a leaf is (), a root with two leaves is (()()), and a three-vertex chain rooted at an endpoint is ((())). Child order is discarded; parent-child structure is preserved.
2. 2. Replace long strings by exact interned IDs. Store a dictionary from vector<int> to a unique integer. When a sorted child-ID vector appears, reuse its existing integer; otherwise assign a fresh one. Equal IDs mean exactly equal vectors. Process vertices bottom-up so every child ID already exists. Crucially, use the same dictionary for both trees and all candidate roots. With separate dictionaries, unrelated shapes might both receive ID 7, and matching numbers would prove nothing. The numeric size of an ID does not indicate depth or size.
3. 3. Why rooted equality is exact. Leaves match because both have the empty signature. Inductively, equal root signatures give a pairing of child subtrees with equal signatures, including their multiplicities. Their inductive isomorphisms can be combined with the root pairing because child subtrees are disjoint. Conversely, a rooted isomorphism must map children to children with the same shape, so it preserves the sorted signature list. This proves both directions; no probabilistic hash assumption is involved.
4. 4. Remove the arbitrary root using centers. A tree has one center or two adjacent centers. Repeatedly remove all current leaves until at most two vertices remain; these are the centers. Any isomorphism preserves distances, hence preserves the center set. Compute the whole-tree rooted signature at each center. Sort the one or two resulting IDs and compare the lists between trees. If a rooted center signature matches, it supplies a valid unrooted isomorphism; if the trees are isomorphic, their center signatures necessarily match. For N=1, the only vertex is the center.
5. 5. Work a relabeling example. Tree A has edges 1–2, 1–3, 2–4, 2–5. Tree B has edges 5–4, 5–3, 4–1, 4–2. Mapping 1→5, 2→4, 3→3, 4→1, 5→2 preserves every edge, so the answer is YES. The actual programs do not guess that permutation. They discover equal center-rooted signatures. By contrast, a five-vertex path and five-vertex star have different center signatures and return NO, despite having the same number of vertices and edges.
6. 6. Know what changes for variants. This lesson ignores labels, edge weights, and the order of children. To preserve vertex colors, include each vertex’s color in its interned key. To preserve edge labels, include the edge label together with each child ID before sorting. For ordered rooted trees, do not sort child signatures. Straight bracket strings can take quadratic copying time on a path; interned IDs avoid repeatedly copying entire subtree descriptions. The implementation computes at most two rootings per tree and traverses iteratively.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<queue>
#include<map>
#include<algorithm>
using namespace std;
vector<int>centers(const vector<vector<int>>&g){
    int n=(int)g.size()-1;
    if(n==1){
        return {1};
    }
    vector<int>degree(n+1);
    queue<int>leaves;
    for(int v=1;v<=n;v++){
        degree[v]=(int)g[v].size();
        if(degree[v]==1){
            leaves.push(v);
        }
    }
    int remaining=n;
    // Peel complete leaf layers to find the unrooted tree center(s).
    while(remaining>2){
        int layer=(int)leaves.size();
        remaining-=layer;
        while(layer--){
            int v=leaves.front();
            leaves.pop();
            for(int u:g[v]){
                if(--degree[u]==1){
                    leaves.push(u);
                }
            }
        }
    }
    vector<int>result;
    while(!leaves.empty()){
        result.push_back(leaves.front());
        leaves.pop();
    }
    return result;
}
int rootedID(const vector<vector<int>>&g,int root,map<vector<int>,int>&dictionary){
    int n=(int)g.size()-1;
    vector<int>parent(n+1),order{root},id(n+1);
    for(int i=0;i<(int)order.size();i++){
        int v=order[i];
        for(int u:g[v]){
            if(u!=parent[v]){
                parent[u]=v;
                order.push_back(u);
            }
        }
    }
    // Bottom-up interning: all child structural IDs are ready before the parent.
    for(int i=n-1;i>=0;i--){
        int v=order[i];
        vector<int>key;
        for(int u:g[v]){
            if(parent[u]==v){
                key.push_back(id[u]);
            }
        }
        sort(key.begin(),key.end()); // Unordered children.
        auto it=dictionary.find(key);
        if(it==dictionary.end()){
            int fresh=(int)dictionary.size()+1;
            it=dictionary.emplace(key,fresh).first;
        }
        id[v]=it->second;
    }
    return id[root];
}
int main(){
    int n;
    cin>>n;
    vector<vector<int>>a(n+1),b(n+1);
    for(auto*g:{&a,&b}){
        for(int i=1,u,v;i<n;i++){
            cin>>u>>v;
            (*g)[u].push_back(v);
            (*g)[v].push_back(u);
        }
    }
    // Shared dictionary: equal numeric IDs have equal structural meanings.
    map<vector<int>,int>dictionary;
    vector<int>idsA,idsB;
    // Isomorphisms preserve centers; try the one or two canonical root positions.
    for(int c:centers(a)){
        idsA.push_back(rootedID(a,c,dictionary));
    }
    for(int c:centers(b)){
        idsB.push_back(rootedID(b,c,dictionary));
    }
    sort(idsA.begin(),idsA.end());
    sort(idsB.begin(),idsB.end());
    cout<<(idsA==idsB?"YES":"NO")<<'\n';
}

Complexity analysis

O(N log N) worst-case time and O(N) stored data for these at most four rootings. Sorting child lists totals O(N log N). A dictionary lookup has O(log N) vector comparisons; charging each comparison to the searched key length plus one gives O(N log N) total because child-key lengths sum to N−1 per rooting. This implementation does not claim the linear bound of specialized AHU implementations.

Example input and output

N, then N−1 edges for the first tree and N−1 edges for the second. Both are valid N-vertex trees. Output YES or NO.

Input

5
1 2
1 3
2 4
2 5
5 4
5 3
4 1
4 2

Output

YES

The trees differ only by relabeling; the mapping described in the lesson preserves their edges.

Practical applications

Deduplicating tree shapes, comparing hierarchical structures, symmetry detection, and recognizing repeated subtrees. The same rooted signatures can group identical subtree patterns inside one larger tree.

Check your understanding

Why must both trees use the same signature dictionary?

Put it into practice

Count how many distinct rooted subtree shapes occur when rooting one tree at vertex 1.