Introduction

Finding symmetries of a tree means finding automorphisms: ways to map the tree onto itself while preserving adjacency. For trees, this is much easier than for general graphs because trees have no cycles and admit clean canonical representations. The practical algorithm is to root the tree at its center, compute canonical signatures for subtrees, and then use repeated identical signatures to detect where symmetric swaps are possible.

Step 1: Find the Tree Center

For an unrooted tree, symmetry should be analyzed from the center, not from an arbitrary node. A tree has either:

• one center node
• two adjacent center nodes

You can find the center by repeatedly peeling leaves until one or two nodes remain.

Why this matters: if you root the tree at a random leaf, the encoding of the tree depends on that arbitrary choice and hides global symmetry.

Step 2: Build a Canonical Form Bottom-Up

Once the tree is rooted at its center, compute a canonical signature for every subtree. A standard idea is:

1. compute the signatures of all children
2. sort the child signatures
3. wrap the sorted list in parentheses

A leaf gets the signature ().

Example Python code for a rooted tree signature:

1def canonical_signature(node, parent, graph):
2    child_sigs = []
3    for neighbor in graph[node]:
4        if neighbor != parent:
5            child_sigs.append(canonical_signature(neighbor, node, graph))
6    child_sigs.sort()
7    return "(" + "".join(child_sigs) + ")"

If two rooted subtrees have the same signature, they are isomorphic.

Step 3: Use Repeated Child Signatures to Detect Symmetry

The signature itself tells you where symmetry exists. If a node has several children with identical subtree signatures, those children can be permuted without changing the tree.

For example, if a node has child signatures:

(), (), (()()), (()())

Then:

• the two leaf children are interchangeable
• the two (()()) subtrees are interchangeable

Those repeated groups are the source of automorphisms.

This is why canonical labeling is powerful: it converts the structural question into grouping equal subtree encodings.

Mirror Symmetry as a Simpler Case

Sometimes the real question is only whether the tree is symmetric with respect to a reflection, not the full automorphism group. In that simpler case, the test is:

• root at the center
• at each node, child subtrees must be pairable by identical signatures
• if there is one unpaired child, that child must itself be symmetric around its own root

A recursive check can express this idea.

1from collections import Counter
2
3def is_symmetric_root(node, parent, graph):
4    sigs = []
5    child_info = []
6
7    for neighbor in graph[node]:
8        if neighbor != parent:
9            sig = canonical_signature(neighbor, node, graph)
10            sigs.append(sig)
11            child_info.append((neighbor, sig))
12
13    counts = Counter(sigs)
14    odd_groups = [sig for sig, count in counts.items() if count % 2 == 1]
15
16    if len(odd_groups) > 1:
17        return False
18    if len(odd_groups) == 0:
19        return True
20
21    odd_sig = odd_groups[0]
22    odd_child = next(child for child, sig in child_info if sig == odd_sig)
23    return is_symmetric_root(odd_child, node, graph)

This checks a reflection-style symmetry, not every automorphism.

Counting Symmetries

If you want the number of automorphisms rather than just detecting symmetry, identical child groups matter again. If a node has k children with the same subtree signature, those subtrees can be permuted in k! ways, multiplied by the automorphism counts inside each child subtree.

That leads to a dynamic-programming style count on the rooted tree.

The full counting logic is more involved, but the main insight is simple: equal canonical subtree types are what create permutations.

Complexity

With a reasonable implementation, canonical labeling on a tree is efficient. The expensive-looking part is sorting child signatures, but the total work is still manageable because each edge participates only once in the rooted traversal.

For ordinary tree sizes, this is dramatically better than trying all node permutations, which becomes infeasible almost immediately.

Common Pitfalls

The most common mistake is rooting the tree arbitrarily. For unrooted symmetry, you need to start at the tree center or the result can be misleading.

Another mistake is brute-forcing permutations of vertices. Trees allow much better structure-aware algorithms based on canonical forms.

Developers also often mix up two questions: whether the tree has any nontrivial symmetry versus how many automorphisms it has. The second problem is richer and needs counting logic.

Finally, be careful about rooted versus unrooted trees. A symmetry that preserves an unrooted tree may disappear once you force a specific root.

Summary

• Find the tree center first for unrooted symmetry analysis.
• Compute canonical subtree signatures bottom-up.
• Identical child signatures reveal interchangeable subtrees and therefore symmetries.
• Reflection-style symmetry can be checked recursively from grouped child signatures.
• Full automorphism counting builds on the same canonical-form idea without brute-forcing permutations.