Could someone please provide a reference giving an algorithm to generate uniformly random binary trees?
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.