# Generation of random binary trees

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.

• What distribution on binary trees do you want? – D.W. Feb 28 '14 at 0:42
• I simply want to be able to pick any of the total number of different binary trees with n end nodes with equal probability. – Mok-Kong Shen Feb 28 '14 at 13:59

Binary trees are counted by Catalan numbers: the number of "full" binary trees (each node has either 0 or 2 children) with $n$ leaves is $C_{n-1}$. The Catalan numbers are given by an explicit formula, and also satisfy the recurrence $$C_{n+1} = \sum_{i+j = n} C_i C_j,$$ which follows directly from the interpretation as counting binary trees. You can use this formula to decode a number in $[0,C_{n-1}) = \{0,\ldots,C_{n-1}-1\}$ to a binary tree. If the index is chosen randomly, you obtain a random binary tree.
The decoding procedure is recursive. First, we partition $[0,C_{n-1})$ into intervals of lengths $C_0 C_{n-2}, C_1 C_{n-3}, \ldots, C_{n-2} C_0$. If the number falls in the interval of length $C_i C_j$, then the left subtree will have $i+1$ leaves, and the right subtree will have $j+1$ leaves. Within the interval, we have an index in the range $[0,C_i C_j)$, which we decode to a pair of indices $x \in [0,C_i)$ and $y \in [0,C_j)$. We recursively compute which tree with $i+1$ leaves is encoded by $x$ and which tree with $j+1$ leaves is encoded by $y$. The recursion stops when $n = 1$, in which case the tree consists of just the root.
• (1) The semantics of the individual terms is described in the second paragraph: the summation conditions on the distribution of leaves among the two children of the root. If the sum were expressed in a different form then you would get a different encoding. Indeed, the order of the terms is not significant, and there are many ways of realizing $[0,C_iC_j) = [0,C_i) \times [0,C_j)$. (2) It's better if you worked it out yourself. Try to understand how the basic formula works in this case, and then try to see how it can be used for encoding trees. – Yuval Filmus Mar 2 '14 at 16:00