# Numbering of unlabelled trees

For labelled trees there are the Pruefer numbers that uniquely identify them. Is there a similar numbering system for unlabelled trees?

• Are these binary trees, or arbitrary trees? Commented Oct 19, 2013 at 8:04
• If there is a numbering system for binary trees, I would also be very interested in it. Commented Oct 20, 2013 at 20:07

According to Wikipedia, a closed-form formula for the number of unlabelled trees is not known, so a numbering in the form of a bijection between the set of unlabelled trees on $$n$$ vertices and $$\{1,\ldots,T_n\}$$ (for an appropriate $$T_n$$) is probably hopeless. Tree isomorphism is in P, so if you want an "effectively unique" identifier for trees, you can get it by using the Prüfer numbering and applying the algorithm to test equality. It is also possible that you can canonicalize trees (using the same ideas as in the algorithm), thereby creating a coding scheme in which two isomorphic trees get the same (Prüfer) number.