Generate all possible subtrees of a binary tree

Question

I have a binary tree and I want to generate all possible subtrees from it. Example :

   1
  /  \
2     3 
     /  \
    4    5 

The possible output will be:

1, 2, 3, 4, 5.
(1,2) (1,3) 
(1,3,4) (1,3,5) 

Is this possible ? I need an algorithm to generate the output ?

Answer 1

Phylogenetics has to do this a lot.

Programs like phyml solve this problem:

Given:

• A model of evolution (how likely mutations are, etc.)
• Genetic sequences of several current species (from which you find a matrix of evolutionary distances between every pair)

Find: The maximum likelihood evolutionary tree.

You start with a guess, and search tree-space looking for an arrangement that has a higher likelihood according to your model. Stop when you hit a local minimum. Try again for a few different starting trees, to hopefully find a global minimum.

Lots of code to iterate over possible trees has been written for phylogenetics, so that's a good place to look for ideas if you need something like this.

---

My own all SPR library (and example frontend) can give you every possible tree reachable with one subtree prune/regraft, for a given starting tree. It only does tree re-arrangement, and doesn't have the code littered with likelihood calculation. I wrote it a long time ago, some in 2004 and some in 2007, but it's still probably more readable than typical phylogenetics software written by non-programmers.

I sort of finished it, and I think some of the code may have found its way into procov. I think having procov use this library was the idea when I started writing it.

It's not polished, the code is a bit messy, and I basically made up the API as I was writing it. People that use it will probably need to customize it. I tidied up some of the most-confusing parts, since it seemed I never committed my last few changes ~8 years ago.

Anyway, for a given tree, there's a theoretical max number of possible SPRs, many of which will produce duplicate trees.

• Given a number in this range, spr.c: spr_sprnum(struct spr_tree *tree, int coded_sprnum) decodes it into an SPR, and tries to apply it.

• spr.c: int spr_next_spr( struct spr_tree *tree ) tries numbered SPRs until it finds a legal one, or comes back to the beginning.

It remembers which SPR it just did, so it first undoes the last SPR, then does the new one.

To iterate over all SPRs in random order, my code finds a linear congruential generator that will generate all numbers from 1 to N exactly once, and then repeat. Finding the LCG parameters requires finding appropriate prime numbers, so there's a simple sieve of Eratosthenes in there in lcg.c

brontler is a demo frontend that can take a tree in Newick format on the command line or from a file. e.g.

./brontler '(((a,b),c),(d,e))'
tree: taxa: 5, nodes: 9, possible SPRs <= 72
1: tree 1.45: (c,(((a,b),d),e));
2: tree 1.10: (a,((b,c),(d,e)));
3: tree 1.59: (c,(d,((a,b),e)));
4: tree 1.29: (((a,c),b),(d,e));
5: tree 1.60: ((b,c),(d,(a,e)));
6: tree 1.61: ((a,c),(d,(e,b)));
7: tree 1.69: (((a,(b,e)),c),d);
8: tree 1.53: ((((d,a),b),c),e);
9: tree 1.46: ((b,c),((a,d),e));
10: tree 1.54: (e,((a,(d,b)),c));
11: tree 1.68: (d,(((a,e),b),c));
12: tree 1.47: ((a,c),((d,b),e));
tree iteration 1 gave 12 new trees

With debugging -d 1 or higher, you will see names of internal nodes in the output. They're upper-case single letters, assigned in sequential order as the tree is parsed. (And will get weird beyond Z, because I just increment a char variable...)

It's GPLv2, and I'd probably make it LGPL if anyone had a good reason and asked nicely. It's not a complicated algorithm or design, so don't worry about reimplementing parts of it if you don't want to use the code directly.

Answer 2

Let's me post the answer in pseudocode:

first let me show you how i implement three:

Node{
 Node rightNode;
 Node leftNode;
 String value;
}

And after this is the algoritm:

Algoritm{
    String[] posibleThrees;

    String getPosibleThrees(Node root){
        getPosibleThree(root, "");
        return posibleThrees;
    }

    void getPosibleThree(Node node, String nodesBefore){
        posibleThrees[] = nodesBefore; //adding nodes before

        if (node.rightNode != null){
            getPosibleThree(node.rightNode, nodesBefore+" "+node.value);
        } 

        if (node.leftNode != null) {
           getPosibleThree(node.leftNode, nodesBefore+" "+node.value);
        }
    }
}