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 [0.0, 1.0) as (relative) frequencies of n symbols for generating a Huffman tree (used in 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 symbols would be highly suppressed in the generation process. If this is correct, how could one do better? Thanks in advance.