Generating all possible binary trees given n leaves

Question

So as the title suggests anyone has/ knows of an algorithm (in java if possible)to generate all possible binary trees given the number of leaves as in the example of the second link below?

` N                  N                  N
 / \                / \                 /\
N   N               N  N               N  N
/\   /\             /\                     /\
N  N  N N           N  N                    N N
                   / \                        /\
                   N  N                       N N

I´ve already been to this , this, this and this but I have tried to implement each and they don´t do what I´m looking for or not explained properly. The first one would be a lot of computation if I have to first generate all possible strings and then parse them to tree type (parent-children relation) and the second one does not print all trees. Because, for instance if I execute by specifying 3 internal nodes like the example above, it just prints one tree(the one on the left). I know from researching about Catalan numbers that even for a small number of nodes the number of trees grows by a lot but is a useful tool for low number of nodes.

Just wondering: what is the problem you are trying to solve by figuring the possible "permutations" of objects in binary trees? — GhostCat, Aug 17 '16 at 16:00
@GhostCat maybe he's trying to find the "optimal" iteration? But then again, the way to solve that would simply be to balance the tree — Nick Zuber, Aug 17 '16 at 16:21
@GhostCat right, well I´m building an Ai for a game in which you play with trees and I want it to have all possibilities but in later stages of the game discard trees which are not useful. — Enixf, Aug 17 '16 at 16:21
The way you're describing the problem it could have infinite solutions ... — raven, Aug 17 '16 at 16:29
@Roberto De La Parra sorry, maybe I didn´t explain myself properly. But not really as you will only have as number of solutions the nth Catalan number given by (2n)! / (n+1)!n!. So for n = 4 (in this case n is the number of internal nodes) there are 14 possible trees ( see first link). so the Ai knows I have any of those 14 trees. — Enixf, Aug 17 '16 at 17:01

score 4 · Accepted Answer · edited Dec 13 '21 at 05:55

No, I don’t know of an algorithm, but I can’t think it would be too hard devising one:

List<TreeNode> allBinaryTrees(int numberOfLeaves) {
    if (numberOfLeaves < 1) {
        throw new IllegalArgumentException("Number of leaves must be positive");
    }
    List<TreeNode> result = new ArrayList<>();
    if (numberOfLeaves == 1) {
        // return a single tree consisting of a single leaf node
        result.add(new Leaf());
        return result;
    }
    for (int sizeOfLeftSubtree = 1; sizeOfLeftSubtree < numberOfLeaves; sizeOfLeftSubtree++) {
        List<TreeNode> possibleLeftSubtrees = allBinaryTrees(sizeOfLeftSubtree);
        List<TreeNode> possibleRightSubtrees = allBinaryTrees(numberOfLeaves - sizeOfLeftSubtree);
        for (TreeNode lt : possibleLeftSubtrees) {
            for (TreeNode rt : possibleRightSubtrees) {
                // make a tree of a node with lt and rt as subtrees,
                // and add it to the result
                result.add(new InternalNode(lt, rt));
            }
        }
    }
    return result;
}

In the above I have assumed that InternalNode and Leaf are both subclasses of TreeNode.

Generating all possible binary trees given n leaves

1 Answers1