# How to efficiently compute all trees with n leaves and 2n-2 nodes

I would like to efficiently compute all trees with n leaves and 2n-2 nodes. This is equivalent to trees with n leaves where all interior (non-leaf) vertices are trivalent.

The input should be the number n and the output should be a list consisting of graphs.

For example, the output for 6 would be:

Ideally I would like to be able to compute up to n=19 or 20. This would give 11020 trees.

Right now I have an extremely slow method which starts from a tree with n leaves and one central node, and then "grows" the interior edges in all ways, and then removes the isomorphic / redundant trees in the end. This allows me to go up to n=10.

Update: Here is the best I have come up with so far...

First there is a command for making a tree object into a graph object (see another one of my questions).

    makeTree[nodes_] :=
Module[{counter = 0},
traverse[h_[childs___]] :=
With[{id =
counter}, {UndirectedEdge[id, ++counter],
traverse[#]} & /@ {childs}];
traverse[_] := Sequence[];
Graph[#] &@Flatten[traverse[nodes]]]


Then I make all rooted trees using Groupings:

   AllRootedTrees[n_] :=
makeTree /@ TreeForm /@ Groupings[Table[a, n - 1], {2, Orderless}]


Then, I remove the isomorphic duplicates:

  AllTrees[n_] :=
DeleteDuplicates[AllRootedTrees[n], IsomorphicGraphQ[#1, #2] &]


The last step is probably very inefficient but this is the fastest method I have so far.

(the computation for 15 trees takes 25.2 seconds)

• It seems that you have a non-recursive algorithm to generate the trees -- can you make it recursive? Meaning, can you turn your current algorithm to find n-level trees from (n-1)-levels trees? Can you post your code? – Anton Antonov Jul 12 '17 at 15:15
• For the last step, use DeleteDuplicatesBy[trees, CanonicalGraph]. It will be much faster because it does not do pairwise comparisons. – Szabolcs Nov 14 '18 at 20:02

I think your code is good. The serious bottleneck is removing isomorphic duplicates. The efficient way to do this is

DeleteDuplicatesBy[graph, CanonicalGraph]


CanonicalGraph will canonically order/label vertices, so that it always maps isomorphic graphs to the same expression (which is also a Graph).

With this sole change,

AllTrees[n_] := DeleteDuplicatesBy[AllRootedTrees[n], CanonicalGraph]


the timing is

AllTrees[20] // Length // AbsoluteTiming
(* {39.6098, 11020} *)