# How to generate uniformly random binary trees?

Could someone please provide a reference giving an algorithm to generate uniformly random binary trees?

• If you are familiar with generating functions, have a look at Boltzmann sampling. It is a very powerful method of sampling discrete objects, such as binary trees.
– Juho
Commented May 7, 2013 at 19:41
• What exactly are you looking for? Trees are different if their "structure" is different? Trees are labelelled trees? You want tress restricted to a specific number of nodes $n$? If not restricted to a specific number of nodes, what exactly do you mean by uniformly random? Commented May 7, 2013 at 23:56
• You could aslo start with any binary tree and the perform randomly rotations. However the mixing time (or to be more precise the best bounds that are known) for this process is bad. (I cant recall the papers, but if you want to go in this direction I can look it up for you.) Commented May 8, 2013 at 7:57
• I mean, if I have the ensemble of all trees satisfying a certain condition (here binary and having n terminal nodes), I could pick one of them randomly. (I am not sure whether it is practically meaningful to consider all trees with node numbers unlimited, i.e. up to infinity.) Commented May 8, 2013 at 9:01

There is a article available here and survey available here

But desipte that its very easy to generate such tree, it all depends on random generator, it must be uniform.

There are two simple approaches:

• Generate full tree up to some height and randomly cut edges
• Start from root and make decision about each child on lower level

Both of them are guarantee to end, fist one is obvious, second one needs some induction proof which is quite simple to do.

Taking into account Juho's hint take a look at Boltzmann sampling, it is indeed a powerfull tool which you can use. And here's a working example.

• Would it be feasible to additionally require that there be n terminal nodes? Commented May 7, 2013 at 20:09
• Its not a must because according to laws of probability tree will terminate sooner or later (unless vertice probability is 1), it just might be very deep. But you might add restriction on number of nodes. Commented May 7, 2013 at 21:22
• The survey seems to have bit-rotted a little (or at least my viewer did not like the .ps inside the tarball). There is an alternative version at sis.uta.fi/cs/reports/pdf/A-1998-3.pdf Commented Mar 2, 2017 at 11:29