mapping integers to k-ary trees

Question

Is there an algorithmic way to map the natural numbers to unique k-ary trees?

I am familiar with the work of Tychonievich who created a mapping from integers to binary trees. https://www.cs.virginia.edu/~lat7h/blog/posts/434.html

Is there something similar for k-ary trees?

There is more than one way to count k-ary trees, meaning that the numeric values will be different (there are different equivalence relations...). Would you spell your definition explicitly in your Question? — Wlod AA, Commented Nov 22, 2019 at 4:20
It seems that you can follow the 2-ary solution from the link you have provided. I don't see any complication, the generalization seems to be straightforward. — Wlod AA, Commented Nov 22, 2019 at 4:50
I have tried extending it to the case of an n-ary tree and encountered a complication. At the end of the algorithm suggested by Tychonievich, he splits the integer into two separate integers, one for the right child and another for the left child. If I have an n-ary tree, it is not clear how many children there would be. — Sohrab T, Commented Nov 22, 2019 at 17:53
Do everything by analogy. You'll use base k notation. You'll have k children each time (some of them may be empty, corresponding to digit 0. (I better go back to that link and have another look). — Wlod AA, Commented Nov 22, 2019 at 18:24
Yes, given a non-negative integer, you extract k new integers (corresponding to children) by collecting the digits on the position = r mod k to form the r-th integer. — Wlod AA, Commented Nov 22, 2019 at 18:34

Brendan McKay · Accepted Answer · 2021-08-14 08:42:15Z

3

If you search for "ranking $k$-ary trees" or "ranking $t$-ary trees" you will find several published papers on this. For example:

answered Aug 14, 2021 at 8:42

Brendan McKay

37.7k3 gold badges80 silver badges147 bronze badges

Add a comment |

1 Answer 1