# Comparing two rooted n-ary trees irrespective of the order of children nodes?

I want to compare two trees: I will consider the trees equal if they are:
Isomeric-i.e have the same structure.
Nodes in both trees have the same values but the order of the children nodes are not necessarily the same.
A picture is worth a thousand words: eg:

A)                B)              C)                D)
(2)                (2)               (2)                  (2)
/  |  \            /  |  \           /  |  \              /  |  \
(4) (5) (7)        (5) (7) (4)       (5) (4) (7)          (5) (4) (7)
|   |              |       |         |   |                |   |
(3) (7)            (7)     (3)       (7) (3)              (3) (7)
/ \            / \               / \                      / \
(0) (1)       (1) (0)           (0) (1)                  (0) (1)

Trees A), B) and C) are equal.
Tree D) isnt equal to any of the trees due to subtrees:
(5) and  (4)
|        |
(3)      (7)
/ \
(0) (1)


I have already looked at the classical linear time algorithm for rooted tree isomorphism due to Aho, Hopcroft and Ullman but his algo only checks for structure but doesnt account for contents/values in the respctive nodes. link

I was wondering if its possible to incomporate the comparison of the actual node values into this algorithm?

A trivial algorithm will be to sort children nodes for all nodes seriallize the resulting tree for both trees then a simple comparison might suffice.

I was wondering if there exist a more eficient way of accomplishing this.

Update: NODE values are not distinct and could be repetive.

• (In addition to the answer, just in case you miss the following point) In related problems, isomorphism complicates things exactly because the labels in the graphs can be different. When the labels must match, the problem is just to check that the graphs are exactly the same (i.e. have the same adjacency matrix), which is trivial. In particular, Graph isomorphism, currently not known to be in P, becomes trivial with the additional requirement that the labels must match. Dec 20, 2022 at 0:02
• @Dmitry that answer assumes that the node values are distinct. What if the node values could be repetitive? Dec 20, 2022 at 15:53
• I see, I missed that. Then you should just modify the Aho's algorithm. The modification is trivial: if $\ell$ is the node's label and $x$ is the node's number generated by the algorithm, then in the algorithm, instead of $x$ use tuple $(x,\ell)$ for comparisons (compere tuples lexicographically). Dec 20, 2022 at 16:18
• @Dmitry will this affect the time complexity signinficantly. I know originally Aho's algo can me optimized to linear time complexity. Would that be possible when i include this modification? Dec 20, 2022 at 17:48
• It'll take $O(n \log n)$ time due to sorting (their algorithm also uses sorting, but it can be done in linear time using counting sort). The main subproblem to solve is "given two arrays, do they have the same elements?". For this subproblem, I suspect that $\Omega(n \log n)$ is theoretically required. In practice, you can get $O(n)$ with hashmaps. Dec 20, 2022 at 18:11

• Well, yes, otherwise it's just tree isomorphism again. If every vertex can be labelled 1. I assumed, since OP had labelled the $n$ nodes from $1,...,n$ that they were unique. Maybe I'm mistaken. Dec 20, 2022 at 10:50