Suppose I have $n1$ distinguishable labels for internal nodes $A=\{a_1, a_2,\dots, a_{n1}\}$ 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?

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 (n1)!*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)
When you compare whether T1 and T2 are equal, you can again use recursion.
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. 


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 doublecounting 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. 


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_{i}s 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_{1}b_{1}b_{2}b_{2}...b_{n1}b_{n1}b_{n}b_{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^{n} ways to pick that. We can incorporate this into our earlier counting method by looking at anagrams of the 2n distinct letters b_{1}c_{1}b_{2}c_{2}...b_{n1}c_{n1}b_{n}c_{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_{i}s as b_{i}s, 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. 


The paper "Binary Tree Gray Codes" by Proskurowski and Ruskey, in the Journal of Algorithms http://dx.doi.org/10.1016/01966774(85)900409 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. 

