Why Encode a Rooted Tree?
A rooted tree can have many different vertex labels, and its children have no prescribed order. A useful isomorphism test must therefore ignore labels and must not treat two different drawings or listings of the children as different trees. We will assign a parenthesis string to each rooted tree, working from the leaves toward the root. The code records the shape below each vertex, while sorting child subtrees by a fixed rule makes the result independent of how those children happen to be listed.
All trees in this tutorial are finite, nonempty, and simple. A rooted tree is a tree with one distinguished vertex called its root. Orienting each edge away from the root gives each non-root vertex a unique parent; the vertices immediately below a vertex \(v\) are its children. The rooted subtree at \(v\) consists of \(v\) and all its descendants, rooted at \(v\). Two rooted trees are rooted-isomorphic if there is a bijection of their vertex sets that preserves adjacency and maps one root to the other. The children are unordered: an isomorphism need not preserve any listing of them.
Defining the Canonical Code
For a vertex \(v\), let \(h(v)\) be the maximum number of edges in a path from \(v\) down to a descendant. Let \(q(v)\) be the number of children of \(v\). We define the code \(C(v)\) recursively. A leaf has code \(()\). For a non-leaf, first compute the codes of the child subtrees, put them in the fixed order defined below, concatenate them, and enclose the result in parentheses.
This is one particular deterministic ordering; it is not ordinary lexicographic ordering of the parenthesis characters. Any fixed total order on rooted subtree types would serve for the isomorphism test, provided it is used consistently. The structural rule here will be used in every example. The recursive definition is well-founded because each child subtree has fewer vertices than the subtree at its parent. It applies to the one-vertex tree as well: its root is a leaf and its code is \(()\).
The parentheses mark the boundary of a vertex’s code, and each child code appears as a complete block inside that boundary. The code records no vertex labels. In particular, changing labels or changing the order in which children are written cannot affect it.
Worked Example: Sorting Three Different Child Subtrees
Let \(T\) have vertex set \(V(T)=\{r,a,b,c,d,e,f\}\), edge set \(E(T)=\{ra,rb,rc,bd,be,cf\}\), and root \(r\). Thus \(a\) is a leaf, \(b\) has children \(d,e\), and \(c\) has child \(f\). We compute from the leaves upward.
| Vertex or subtree root | Child codes | Code |
|---|---|---|
| \(a,d,e,f\) | None | \(()\) |
| \(b\) | \(()\), \(()\) | \((()())\) |
| \(c\) | \(()\) | \((())\) |
| \(r\) | Sorted below | Computed below |
The child subtrees at \(r\) have heights \(0,1,1\): the subtree at \(a\) has height \(0\), and those at \(b,c\) have height \(1\). So the leaf code \(()\) comes first. Of the two height-\(1\) subtrees, \(b\) has two children and \(c\) has one, so the rule puts \(C(b)=(()())\) before \(C(c)=(())\). The sorted child codes are therefore \(()\), \((()())\), \((())\). Concatenating them and adding the outer parentheses gives
Check: removing the outermost pair from the root code leaves the three complete blocks \(()\), \((()())\), and \((())\), in the prescribed order. The tree has seven vertices: one root, one leaf child \(a\), the three vertices \(b,d,e\), and the two vertices \(c,f\). The subtrees represented by the blocks have respectively \(1,3,2\) vertices, and \(1+3+2+1=7\), as required.
Why Rooted Isomorphisms Preserve the Code
Proof. We use induction on the number of vertices. If a rooted tree has one vertex, its root has no children and its code is \(()\), so the claim holds for a pair of one-vertex rooted trees. Now suppose the result holds for rooted trees with fewer than \(n\) vertices, and let two rooted trees with \(n\) vertices be rooted-isomorphic. A root-preserving isomorphism maps the root’s children bijectively to the other root’s children. For each child, it also maps the entire subtree below that child to the subtree below its image, preserving the root of that subtree. Each such child subtree has fewer than \(n\) vertices, so the induction hypothesis gives equal codes for each matched pair. Thus the two roots have the same multiset of child codes. Sorting the same multiset by the fixed rule produces the same list, and enclosing its concatenation in parentheses gives equal root codes. \(\square\)
The proposition explains why the code is independent of labels and child listing. It also shows why sorting matters: without sorting, the same unordered collection of child subtrees could produce different strings just because the children were written in a different order.
Equal Codes Characterize Rooted Isomorphism
Proof. The forward implication from rooted isomorphism to equal codes is the proposition just proved. For the converse, suppose two rooted trees have equal codes. We prove by induction on the common code’s number of vertices that the trees are rooted-isomorphic. The number of vertices represented by a code is determined by the code: each vertex contributes one matching pair of parentheses. If the common code is \(()\), both trees consist of one root and no other vertices, so mapping one root to the other is an isomorphism.
Now suppose the common code has more than one vertex. Its outermost parentheses enclose the concatenation of the root’s child codes. A parenthesis string formed by this recursion splits uniquely into its top-level child blocks: starting just inside the outer pair, each block ends when its parentheses return to the starting level. Thus equality of the full codes gives equality of the sorted lists of child codes, including their multiplicities. Pair the children in the two trees in the corresponding positions. Each pair has equal codes and represents a strictly smaller rooted tree, so the induction hypothesis supplies a root-preserving isomorphism between the two child subtrees. These subtrees are disjoint, and there are no edges between different child subtrees: such an edge would create a cycle in the original tree. Combining the child-subtree isomorphisms and mapping root to root therefore gives a bijection preserving every edge. It is a rooted isomorphism, as required. \(\square\)
The proof also establishes why the code is a complete invariant: it contains enough information to recover the unordered collection of child-subtree types at every vertex. It is not a drawing or a list of vertex labels; it represents the recursive shape of the tree.
Worked Example: Comparing Two Rooted Trees with Different Labels
Let \(T_1\) have vertex set \(\{r,a,b,c,d,e\}\), edge set \(\{ra,rb,ac,ad,be\}\), and root \(r\). Let \(T_2\) have vertex set \(\{s,u,v,x,y,z\}\), edge set \(\{su,sv,ux,uy,vz\}\), and root \(s\). Both are simple trees; the edge lists give each non-root vertex exactly one parent.
In \(T_1\), the leaves \(c,d,e\) each have code \(()\). Vertex \(a\), with children \(c,d\), has code \((()())\). Vertex \(b\), with child \(e\), has code \((())\). Both child subtrees at \(r\) have height \(1\); \(a\) has two children and \(b\) has one, so their sorted codes are \((()())\), then \((())\). Hence
In \(T_2\), the leaves \(x,y,z\) each have code \(()\). Vertex \(u\) has two leaf children, so \(C(u)=(()())\), while \(v\) has one leaf child, so \(C(v)=(())\). Their order at \(s\) is again \(u\) then \(v\), by the same height and child-count comparison. Therefore
Check: the theorem implies that the rooted trees are rooted-isomorphic. Explicitly, map \(r\) to \(s\), \(a\) to \(u\), \(b\) to \(v\), \(c,d\) bijectively to \(x,y\), and \(e\) to \(z\). This maps each listed edge of \(T_1\) to an edge of \(T_2\), and its inverse also preserves edges.
Worked Example: Different Codes Detect Different Rooted Shapes
Let \(S\) have vertex set \(\{r,a,b,c\}\), edge set \(\{ra,rb,rc\}\), and root \(r\). Let \(P\) have vertex set \(\{w,x,y,z\}\), edge set \(\{wx,xy,yz\}\), and root \(w\). Both have four vertices, but their rooted shapes differ.
In \(S\), all three children of \(r\) are leaves with code \(()\), so the root code is
In \(P\), \(z\) is a leaf, so \(C(z)=()\). Then \(C(y)=(())\), \(C(x)=((()))\), and \(C(w)=(((\,())))\), which as a parenthesis string is \((((())))\). Thus \(C_S(r)=(()()())\) differs from \(C_P(w)=((((())))\).
Check: the code lengths are \(8\) and \(8\), respectively, since each tree has four vertices and contributes four pairs of parentheses. The strings are nevertheless different: the star code has three child blocks inside the root pair, while the path code has one nested block at each level. By the theorem, the rooted trees are not rooted-isomorphic.
Using the Test and Avoiding a Sorting Pitfall
To test two rooted trees, compute each code from the leaves upward, sort the child codes at every vertex by the same structural rule, and compare the root strings. Equal strings certify rooted isomorphism by the theorem; unequal strings certify that no root-preserving isomorphism exists. The procedure works even when the trees have repeated isomorphic child subtrees: equal child codes appear with their full multiplicities in the sorted list.
Common pitfall: sorting the parentheses as ordinary text. The ordering used here is structural, not ordinary lexicographic order on the symbols “(” and “)”. In the first example, the correct order at \(r\) is \(()\), \((()())\), \((())\): the leaf has smaller height, and among the two height-\(1\) subtrees the one with two children comes first. If one instead sorts those strings by ordinary lexicographic order with “(” before “)”, the order becomes \((()())\), \((())\), \(()\), giving the different string \((( ()())(())())\) without the displayed space, namely \(((()())(())())\). That result is not the code defined here. The correction is to use the stated structural comparison consistently; an unspecified or inconsistent sorting convention can make a computed string fail to match the canonical code.
The code is useful whenever rooted trees must be compared without relying on labels, drawings, or child order. Its recursive form makes the test direct: compare the roots only after comparing the recursively encoded pieces below them. When applying it, include every child, retain repeated child codes, and use one fixed sorting rule throughout.
Check Your Understanding
Use the structural ordering and the recursive definition in each question.
- What is the code of a rooted tree consisting of one root with four leaf children?
- A root has two child subtrees, both of height \(2\). The first child has one child at its root, and the second has three. Which child code comes first under the stated rule?
- Explain why a root-preserving isomorphism must map the root’s child subtrees bijectively to the other root’s child subtrees.
- Why does equality of the root codes imply that the sorted child-code lists, including multiplicities, are equal?
- Give an example of two rooted trees with the same number of vertices but different root codes, and explain what structural difference the codes record.