How do I iterate over binary trees?

Suppose I have $n-1$ distinguishable labels for internal nodes $A=\{a_1, a_2,\dots, a_{n-1}\}$ and $n$ distinguishable labels for leaves $B=\{b_1,b_2,\dots, b_n\}$ with $A$ and $B$ disjoint. What is the best way to iterate over all possible binary trees if I label without replacement?

-
Perhaps a better place for this question is StackOverflow! :) –  Kevin H. Lin Nov 1 '09 at 15:38
Did you try looking in Knuth's The Art of Computer Programming volume 4 fascicle 4? I don't have it with me, so I'm not sure whether this is in there. –  Zsbán Ambrus Jul 4 '10 at 23:59
To update the comment of Zsbán Ambrus, Knuth's TAoCP Volume 4 covers this material in detail in Section 7.2.1.6, with references. –  András Salamon Sep 26 '13 at 13:57

Disclaimer: I have no computer science background, this is probably not the fastest method of solving your problem.

It is easy to iterate over all unlabeled binary trees of a given size. (I hope you agree.)

If what you're doing is computing some sum over binary trees, then the easiest way to reduce to this situation might be to first iterate over all unlabeled trees, and then for each unlabeled tree add

1/|Aut(T)|*(sum over all (n-1)!*n! possible labelings of the tree T)

where Aut(T) is the group of automorphisms of the tree. The cardinality of the automorphism group can be computed recursively: one defines a function (in pseudocode)

function Aut(T):
if T == {leaf}:
return 1
T1, T2 <- T.subtree(left), T.subtree(right)
if T1==T2:
return 2*Aut(T1)^2
else:
return Aut(T1)*Aut(T2)


When you compare whether T1 and T2 are equal, you can again use recursion.

function equals(T1,T2):
if T1 == {leaf}:
return T2 == {leaf}
if T2 == {leaf}:
return false
T11,T12,T21,T22 <- T1.subtree(left), T1.subtree(right), T2.subtree(left), T2.subtree(right)
if equals(T11,T21):
return equals(T12,T22)
if equals(T11,T22):
return equals(T11,T22)
return false


If you're not computing a sum but you really want an iterator over all labeled trees, one way could be to implement something similar to this. First iterate over all unlabeled trees, then for each internal vertex of your tree check whether there exists an automorphism switching the left and right subtree. If so, rigidify the tree by imposing the condition that the root at the left subtree should be labeled by a smaller element than the root at the right subtree; sum only over these labelings.

-

Wait, you mean n+1 labels for the leaves and n labels for the internal nodes, right?

Note that such trees are counted by the multinomial coefficient {2n choose 2,2,2,2,...,2} (with n 2s), because their Prüfer codes are exactly the ones containing 2 of all but one of the bis and 1 of the last one. If you take such a Prüfer code and affix to its end the label of the root, then you're just counting anagrams of b1b1b2b2...bn-1bn-1bnbn. I'm not a computer scientist, but these are easy enough to loop through, right?

EDIT: Wait, sorry, this counts full binary trees where left and right children are indistinguishable. I suppose this isn't what you want, is it?

Not too hard to fix, fortunately, since the nodes are already labeled: just decide for each internal node whether the child with the higher label is on the right or left. There are 2n ways to pick that. We can incorporate this into our earlier counting method by looking at anagrams of the 2n distinct letters b1c1b2c2...bn-1cn-1bncn. (There are, of course, (2n)! of these). Given such an anagram, get a binary tree as follows:

First, chop off the last letter, treat the cis as bis, and find the tree with this new string as its Prüfer code. Choose the letter you chopped off to be the root, so every internal node now has two children. To decide which is on the left and which is on the right, ask whether bi came before ci in the original string. If so, the child with the smaller label is on the left; otherwise it's on the right.

-
Also, this yields a proof of the Catalan number formula I'm not sure I'd seen before. By the above argument, there are (2n)! trees with the given set of internal and leaf labels. But on the other hand, there are C_n unlabeled full binary trees, and (n+1)! ways to label the leaves and n! ways to label the internal nodes of each such tree. So (2n)! = C_n*(n+1)!n!. Hah. –  Jonah Ostroff Nov 1 '09 at 20:40

The paper "Binary Tree Gray Codes" by Proskurowski and Ruskey, in the Journal of Algorithms http://dx.doi.org/10.1016/0196-6774(85)90040-9 gives a method of generating all binary trees, so that the successive in the generation differ by a constant amount. It also gives references to previous such algorithms.

-

This seems naturally recursive. For each choice of root and each subset of the internal nodes, you have to generate all possible left subtrees using those internal nodes, and all possible right subtrees using the remaining nodes. For each pair of those, you have to generate all permutations of the leaves.

That's if the left and right branches are considered distinguishable, so if "r(L, R)" means the binary tree with root r, left subtree L, and right subtree R, then r(L, R) and r(R, L) are not the same. On the other hand, if the relation "r(L, R) = r(R, L)" holds, then you can avoid double-counting in the following way: for each choice of root, pair each subset S of the remaining internal nodes with its complement Sc, and out of each pair, pick one to use as the nodes for the left subtree; don't use both it and its complement. You still generate all permutations of the leaves for each pair of left and right subtree.

-