How to generate uniformly random binary trees?

Question

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.
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?
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.)
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.)

Bartek · Answer 1 · 2013-05-07 21:58:25Z

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:

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?
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.

1 Answer