CODEWITHSUNDEEP
javaalgorithmtreebinary-treepermutation
Enixf
Enixf

Reputation: 117

Generating all possible binary trees given n leaves

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.

Upvotes: 2

Views: 3094

Answers (1)

Anonymous
Anonymous

Reputation: 86324

I interpret your requirements in this way: You want all binary trees consisting of internal nodes and leaves where every internal node has exactly two children (no node has only one child) and with the given number of leaves.

And 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;
    }
    // We need one node for the root and at least one for the right subtree,
    // so the size of the left subtree
    // can only go up to numberOfLeaves - 2.
    for (int sizeOfLeftSubtree = 1; sizeOfLeftSubtree < numberOfLeaves - 1; 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. You may want a different design.

Upvotes: 5

Related Questions