5
$\begingroup$

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.

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

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.

$\endgroup$
  • $\begingroup$ Sorry that my poor knowledge doesn't allow me yet to understand your very elegant solution. (1) What does the individual terms in the summation formula signify (semantically)? What if the sum were expressed in a different but equvalent form instead? (2) If it doesn't cause too much work for you, could you please explain the process in some detail for the case of 4 leaves such that it's clear that the 5 different binary trees would have equal probability to be selected? Thanks in advance. $\endgroup$ – Mok-Kong Shen Mar 2 '14 at 8:59
  • $\begingroup$ (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. $\endgroup$ – Yuval Filmus Mar 2 '14 at 16:00
  • $\begingroup$ I am amazed by your knowledge @YuvalFilmus .. I learnt something new today :) $\endgroup$ – AJed Mar 20 '14 at 15:46
1
$\begingroup$

I have found an algorithm on p.16 of the book: L. Alonso, R. Schott, Random Generation of Trees, Kluwer, 1995. Note however that the C code for it on p.191-192 of the book is erroneous (from communication of the first author). (I have coded the algorithm in Python and included it in a program of my own: http://s13.zetaboards.com/Crypto/topic/7164646/1/)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.