How do I iterate over binary trees? - MathOverflow

How do I iterate over binary trees?

2009-11-01T09:29:02Z

Suppose I have n-1 distinguishable labels for internal nodes A={a1, a2, ..., an-1} and n distinguishable labels for leaves B={b1,b2, ..., bn} with A and B disjoint. What is the best way to iterate over all possible binary trees if I label without replacement?

Answer by Dan Petersen for How do I iterate over binary trees?

2009-11-01T12:00:21Z

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.

Answer by Darsh Ranjan for How do I iterate over binary trees?

2009-11-01T19:30:33Z

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 S^c, 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.

Answer by Jonah Ostroff for How do I iterate over binary trees?

2009-11-01T20:09:20Z

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 b_is 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 b₁b₁b₂b₂...b_n-1b_n-1b_nb_n. 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 2ⁿ ways to pick that. We can incorporate this into our earlier counting method by looking at anagrams of the 2n distinct letters b₁c₁b₂c₂...b_n-1c_n-1b_nc_n. (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 c_is as b_is, 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 b_i came before c_i in the original string. If so, the child with the smaller label is on the left; otherwise it's on the right.

Answer by Victor Miller for How do I iterate over binary trees?

2012-04-05T19:58:02Z

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.