How to generate uniformly random binary trees?

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

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.

StackExchange Computer Science Q#11862, answer score: 2