Tree Isomorphism

function treeCanonical(n, edges, root = 0) {
    const adj = Array.from({length: n}, () => []);
    for (const [u, v] of edges) { adj[u].push(v); adj[v].push(u); }

    function canonical(u, parent) {
        const childLabels = [];
        for (const v of adj[u]) {
            if (v !== parent) childLabels.push(canonical(v, u));
        }
        childLabels.sort(); // sort for canonical order
        return '(' + childLabels.join('') + ')';
    }

    return canonical(root, -1);
}

function areIsomorphic(n1, edges1, n2, edges2) {
    if (n1 !== n2) return false;

    // Find centers of each tree
    const findCenters = (n, edges) => {
        const adj = Array.from({length: n}, () => []);
        const deg = new Array(n).fill(0);
        for (const [u, v] of edges) { adj[u].push(v); adj[v].push(u); deg[u]++; deg[v]++; }
        let leaves = deg.map((d, i) => d <= 1 ? i : -1).filter(i => i >= 0);
        let remaining = n;
        while (remaining > 2) {
            remaining -= leaves.length;
            const next = [];
            for (const l of leaves) for (const v of adj[l]) if (--deg[v] === 1) next.push(v);
            leaves = next;
        }
        return leaves;
    };

    const c1 = findCenters(n1, edges1), c2 = findCenters(n2, edges2);
    if (c1.length !== c2.length) return false;

    const forms1 = c1.map(c => treeCanonical(n1, edges1, c)).sort();
    const forms2 = c2.map(c => treeCanonical(n2, edges2, c)).sort();
    return forms1.every((f, i) => f === forms2[i]);
}