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?



How do I iterate over binary trees?
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.


