
Generation of random binary trees
Posted:
Feb 26, 2014 3:34 PM


Given n, I want to randomly generate a binary tree (unlabelled) that has n end nodes. Could someone kindly provide a reference containing an algorithm for doing that?
I attempted to do as follows: From a PRNG obtain n PRNs in [O.0, 1.0) as (relative) frequencies of n symbols for generating a Huffman tree (commonly known in the field of data compression). But, if the PRNs used are uniform, then I think this would highly favour generation of those Huffman trees that are more flat and Huffman trees corresponding to widely different frequencies of the symbolss would be highly suppressed in the generation process. If this is correct, how could one do better? Thanks in advance.
M. K. Shen

