Algorithms on Trees

Part I Basic Algorithms

by

Jaime Rangel-Mondragón
jrangel@sunserver.uaq.mx

 Arturo González-Gutiérrez
 aglez@sunserver.uaq.mx

1) INTRODUCTION

We have nothing to fear and a great deal to learn from trees,
that vigorous and pacific tribe which without stint produces 
strengthening essences for us, soothing balms, and in whose 
gracious company we spend so many cool, silent and intimate hours.
Marcel Proust

A fool sees not the same tree that a wise man sees.
William Blake

Trees are versatile graph structures that have found use in so many applications that they are regarded as the most important data structure in Computer Science. A tree is a connected acyclic graph. Among the filum tree are the so-called rooted trees, which can be defined by the BNF:

tree = {} | {root, {tree___}}

Although we can label the nodes of a tree with data of any type, or indeed a mixture of types, for simplicity we will consider in this work positive integers exclusively as we can always set up a one-to-one correspondence between our actual data type and these numbers in an obvious fashion.
This notebook provides several basic operations on trees along with their application to their enumeration and generation. The final sections will specialize this development to binary trees. Every function is accompanied of short comments and examples of its use. The more important functions are marked as initialization cells so that they are readily available via an initial global evaluation of the notebook. 
In what follows we will denote by t a generic tree, by r a generic root and by sT a generic list of subtrees.

Function treeQ below validates a given structure representing a tree.

treeQ[{leaf_, {}}] := True
treeQ[{_, {sT__}}] := And  @@  treeQ  /@  {sT}
treeQ[_] := False

treeQ[1]

treeQ[{1, {}}]

The following tree, affectionately called smallTree, is the first of three examples that will be used to test the algorithms developed throughout this work.

Its extended notation is:

smallTree = {4, {{1, {}}, {5, {{3, {}}, {6, {}}}}, {2, {}}}};

treeQ[smallTree]

2) SHORT NOTATION

The extended notation used above to describe trees, while in accordance with the definition, results awkward in the practice. In order to clarify the output and speed up the input of algorithms dealing with trees, we now design functions shortNotation and longNotation (acting as post and pre-processors of arborescent data respectively) to cater for the algorithms wherein the extended tree notation is advantageous and that we will assume is used internally exclusively throughout. 
In looking at the example following the definition of function shortNotation below, we illustrate the shortening of the extended notation in the case of smallTree by writing leaves as single numbers and eliminating external brackets and substituting the remainder ones by parenthesis thus forming a string structure.

shortNotation[{leaf_, {}}] := ToString[leaf]
\(shortNotation[{r_, {sT__}}] := 
      ToString[r] <> 
        StringReplace[
          ToString[
            shortNotation\  /@ \ {sT}], {"{" -> "(", "}" -> ")", " " -> ""}]\)

smallTree
shortNotation[%]

A straightforward implementation of the transformations dealing with the conversion to the extended notation, which we will call the long notation of a given tree involves the matching of several patterns which Mathematica´s inner mechanism facilitates.

\(longNotation[t_String] := 
      Module[{u}, 
u = 
          Map[If[DigitQ[#], ToExpression[#], #] &, 
            Characters[t]]; 
u = 
          u\  //. \ {xxa___, xxi_Integer, xxj_Integer, xxb___} -> {xxa, 
                10\ xxi\  + \ xxj, xxb}; 
ToExpression[
          sN[ToString\  /@ \ u]]]
		\)
\(sN[{r_, "(", sT__, ")"}] := 
      Module[{c = {sT}, i, j = 1, u, 
          sons = {}}, 
Do[
If[\((c[[i]] == ",")\)\  && \ 
              balanced[u = Take[c, {j, i - 1}]], AppendTo[sons, u]; 
            j = i + 1], {i, Length[c]}]; 
AppendTo[sons, 
          Take[c, {j, Length[c]}]]; 
{r, 
          sN\  /@ \ sons}]\ 
\)
\(sN[{leaf_}] := {leaf, {}}
\)
\(balanced[s_] := 
      Module[{i = 
            0}, 
Map[
If[i < 0, 
              Return[False], 
If[\((# == "(")\)\  || \ \((# == "{")\), \(i++\), 
If[\((# == ")")\)\  || \ \((# == "}")\), \(i--\)]]] &, 
          s]; 
\((i == 0)\)]\)

In showing the use of function longNotation, we introduce the new benchmark trees bigTree1 and bigTree2; a graphic display of them follows; the means to achieve this representation will be given at the end of the following section. We take now the oportunity to verify the use of the long and short notations on them.

\(bigTree1 = 
      longNotation["5(10(8),3(11,12(2(13,14(15,16,17,18))),7),9(1,6),4)"]\)
shortNotation[%]

bigTree2 = 
      longNotation["1(5(11,10(18),12),4(9),2(6(13(19,20,21))),3(7(14,15),8(\
16,17)))"]
shortNotation[%]

3) STRUCTURAL FEATURES

In this section we provide a number of short functions performing useful chores on trees, namely computing the number of nodes, the leaves, the height, the width, the renaming of labels, computing a given subtree and obtaining the set of degrees.

Number of nodes

numNodes[t_] := Length[Flatten[t]]

numNodes[smallTree]

(see the previous diagrams to check this and the following results)

Leaves

leaves[{r_, {}}] := {r}
leaves[{_, {sT__}}] := Flatten[leaves  /@  {sT}]

leaves[smallTree]

leaves[bigTree1]

leaves[bigTree2]

smallTree

Height

height[{_, {}}] := 0
height[{_, sT_}] := 1 + Max[height /@  sT]

height[smallTree]

height[bigTree1]

height[bigTree2]

Width

width[{_, {}}] := 1
width[{_, sT_}] := Plus @@ width  /@  sT

width[smallTree]

width[bigTree1]

width[bigTree2]

Node renaming

rename[t_, newLabels_] := 
      t /. Thread[(#1 -> #2 &)[Flatten[t], newLabels]]

shortNotation[smallTree]

shortNotation[rename[smallTree, Range[numNodes[smallTree]]]]

shortNotation[rename[smallTree, {10, 20, 17, 3, 0, 1}]]

Degrees List

degrees[t_] := 
      Module[{p = toPairs[t], d, i, j}, 
d = 
          Table[0, {numNodes[
                t]}]; 
Map[({i, 
                  j} = #; 
d[[
                  i]] = 
                d[[i]] + 
                  1; 
d[[
                  j]] = 
                d[[j]] + 1) &, 
          p]; 
d]

degrees[bigTree1]

Subtree having root r of tree t

subTree[t_, r_] := t  /;  First[t] == r
subTree[{_, {}}, _] := {}
subTree[{_, sT_}, r_] := 
      Flatten[Map[subTree[#, r] &, sT], 1]

shortNotation[bigTree1]
Table[shortNotation[subTree[bigTree1, i]], {i, 18}]  // 
      TableForm

4) REPRESENTING TREES

Ordered pairs

One way of representing trees is through a set of ordered pairs, i.e., through specifying a relation on its set of nodes. The following functions provide the necessary coding and decoding from this representation. The pairs are given such that (i, j) means that i is the father of  j (Question: in what order do the pairs appear?)

toPairs[{r_, {sT__}}] := 
      Partition[
        Flatten[{Map[{r, #} &, First  /@  {sT}], toPairs  /@  {sT}}], 
        2]
toPairs[_] := {}

toPairs[bigTree1]

toPairs[bigTree2]

In order to design its inverse function taking a set of pairs and computing the corresponding tree, we need to consider the problem of computing the depth of a given node. This chore is performed by function dep below.

dep[r_, {r_, _}] := 0
dep[r_, {_, sT_}] := 1 + Max[dep[r, #] &  /@  sT]

For example, to compute all depths corresponding to bigTree1 we proceed as follows:

shortNotation[bigTree1]
Map[{#, dep[#, bigTree1]} &, Flatten[bigTree1]]

This example says that, for instance, node 14 is of depth 4.

A bit more difficult task is to deduce the depth of a given node n given the pairs forming a tree:

dep2[n_, {a___, {b_, n_}, d___}] := 1 + dep2[b, {a, d}]
dep2[_, _] := 0

p = toPairs[bigTree1];
Map[{#, dep2[#, p]} &, Flatten[bigTree1]]

Map[{#, dep2[#, toPairs[bigTree2]]} &, Flatten[bigTree2]]

Finally, to build up a solution to our inverse problem based on the use of patterns, we need to reorder the given pairs in a depth-wise manner so that we construct the tree in a bottom-up fashion. This procedure is called goodSort.

goodSort[p_] := 
      Sort[p, (dep2[First[#1], p] ≥ 
              dep2[First[#2], p]) &]

goodSort[toPairs[bigTree1]]

Function fromPairs below implements an elimination-construction process whereby the tree is build upon. We then proceed to check the main functions of this section on our benchmark trees.

fromPairs[p_] := 
      Module[{q = goodSort[p], t = {}, i, 
          j}, 
Map[({i, j} = #;  
t = 
                t /. {{xxa___, {i, {xxk__}}, 
                        xxb___} -> {xxa, {i, {xxk, {j, {}}}}, 
                        xxb}, {xxa___} -> {xxa, {i, {{j, {}}}}}}) &, 
          q]; 
First[
          t  //.  {xxa___, {xxb_, xxc_}, 
                xxd___, {xxe_, {xxf___, {xxb_, {}}, xxg___}}, 
                xxh___} -> {xxa, xxd, {xxe, {xxf, {xxb, xxc}, xxg}}, 
                xxh}]]

shortNotation[smallTree]
shortNotation[fromPairs[toPairs[smallTree]]]

shortNotation[bigTree1]
shortNotation[fromPairs[toPairs[bigTree1]]]

shortNotation[bigTree2]
shortNotation[fromPairs[toPairs[bigTree2]]]

Matrices

The conversion of a tree structure into a matrix structure corresponding to the pairs forming the relation father-of has to be acccompanied with an explicit reference to the node we choose to consider the root. Conversely, in order to recover the tree that gave rise to a given matrix, it is necessary to choose the node that will form the root of the required tree. The matrix representation is not unique also in the hierarchical order of the subtrees. Function toMatrix constructs a symmetric matrix, with zeroes in the main diagonal, corresponding to a given tree and, in doing so, mixes the given pairs with its symmetrically positioned twin. Function fromMatrix below disposes of unneeded pairs in order to recover from this mixture by "pulling up" the given root.

\(toMatrix[{r_, sT_}] := 
      Module[{p = toPairs[{r, sT}], m, i, j}, 
m = 
          DiagonalMatrix[
            Table[0, {Length[p] + 1}]]; 
Map[\(({i, j} = #; 
              m\_\(\([[\)\(i, j\)\(]]\)\) = \(m\_\(\([[\)\(j, i\)\(]]\)\) = 1\))\) &, p]; 
{r, 
          m}]
\)
filterPairs[r_, p_] := {}  /;  Cases[p, {r, _}] == {}
\(filterPairs[r_, p_] := 
      Module[{t = Cases[p, {r, _}], c, q}, 
c = 
          Cases[p, {_, r}]; 
q = 
          Complement[p, t, c]; 
Partition[
          Flatten[{t, Map[filterPairs[#, q] &, Last\  /@ \ t]}], 
          2]]
\)
fromMatrix[{r_, m_}] := 
      fromPairs[filterPairs[r, Position[m, 1]]]

shortNotation[smallTree]
t = toMatrix[smallTree];
{First[t],  Last[t] // MatrixForm}
shortNotation[fromMatrix[t]]
ListDensityPlot[-Reverse[Last[t]], 
        Frame -> False];

shortNotation[fromMatrix[{5,(({{0, 0, 0, 1, 0, 0}, {0, 0, 0, 1, 0, 0}, {0, 0, 0, 0, 1, 0}, {1, 1, 0, 0, 1, 0}, {0, 0, 1, 1, 0, 1}, {0, 0, 0, 0, 1, 0}}))}]]

shortNotation[fromMatrix[{2,(({{0, 1, 0, 0, 1, 1}, {1, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 1, 1}, {0, 0, 0, 0, 0, 1}, {1, 0, 1, 0, 0, 0}, {1, 0, 1, 1, 0, 0}}))}]]

5) TRAVERSING TREES

We present four ways to traverse trees, two of them are the traditional pre-ordering and post-ordering. The third one, called naturalOrder, is inspired in the natural appearance of the leaves along the notation (short or long) of the tree. Finally, the function breathOrder is presented, which visits the nodes in a breath-wise manner as we go down into lower levels.

Preorder

preOrder[r_] := r
preOrder[{r_, sT_}] := Flatten[{r, preOrder /@  sT}]

preOrder[smallTree]
preOrder[bigTree1]
preOrder[bigTree2]

Postorder

postOrder[r_] := r
postOrder[{r_, sT_}] := Flatten[{postOrder /@  sT, r}]

postOrder[smallTree]
postOrder[bigTree1]
postOrder[bigTree2]

Natural order

naturalOrder[t_] := Flatten[t]

naturalOrder[smallTree]
naturalOrder[bigTree1]
naturalOrder[bigTree2]

Note that this order coincides with the preOrder.

Breath order

breathOrder[t_] := 
      Module[{ans = {}, 
          h}, 
FixedPoint[(h = 
                Flatten[#, 2]; 
AppendTo[ans, 
                Select[h, AtomQ]]; 
Select[h, ListQ]) &, 
          t]; 
Flatten[ans]]

breathOrder[smallTree]
breathOrder[bigTree1]
breathOrder[bigTree2]

6) THE LEAST COMMON ANCESTOR

The least common ancestor (LCA) of a pair of nodes i, j is that subtree of a given tree having as root the nearest common node of them. In other words, LCA[i, j] is the smallest tree containing nodes i and j.
We start firstly by designing an alternative non-recursive version of former function subTree which selects the subtree of a given tree having an specified root.

subTree[t_, r_] := 
      Module[{p = First[Position[t, r]], 
          g = t}, 
((g = 
                  g[[#]]) &) /@ 
          Drop[p, -1]; 
g]

Table[shortNotation[subTree[smallTree, i]], {i, 6}]

using the above function we construct the required procedure:

LCA[t_, i_, j_] := 
      Module[{p = toPairs[t], pI, pJ, v = 1}, 
pI = 
          FixedPointList[
            p /. {{___, {xxk_, #}, ___} -> xxk, {___} -> 0} &, 
            i]; 
pJ = 
          FixedPointList[
            p /. {{___, {xxk_, #}, ___} -> xxk, {___} -> 0} &, 
            j]; 
While[! (MemberQ[pJ, 
                pI[[
                  v]]]), v++]; 
subTree[t, 
          pI[[v]]]]

shortNotation[LCA[bigTree1, 7, 1]]

shortNotation[LCA[bigTree2, 14, 17]]

One of the uses of LCA is to compute distances between two nodes i and j in a given tree t:

distance[t_, i_, j_] := 
      Module[{q = LCA[t, i, j], r, p, pI, pJ}, 
r = 
          First[q]; 
p = 
          toPairs[q]; 
pI = 
          FixedPointList[
            p /. {{___, {r, #}, ___} -> r, {___, {k_, #}, ___} -> 
                    k, {___} -> r} &, i]; 
pJ = 
          FixedPointList[
            p /. {{___, {r, #}, ___} -> r, {___, {k_, #}, ___} -> 
                    k, {___} -> r} &, j]; 
Length[
            pI] + Length[pJ] - 4]

distance[bigTree2, 19, 17]

Let us compute the distance matrix for smallTree:

t = smallTree;
ListDensityPlot[-Reverse[Last[toMatrix[t]]], 
        Frame -> False];
n = Length[Flatten[t]];
d = Table[0, {n}, {n}];
\(\(Do[
	
        d[[i, 
            j]] = \(d[[j, 
              i]] = distance[t, i, j]\), {i, n - 1}, {j, 
          i + 1, n}];\)\)
MatrixForm[d]
ListDensityPlot[-Reverse[d], Frame -> False];

We can recognize the original tree as the portion in gray in the above picture.

With the help of distances we can compute the centers (or center) of a given tree defined as those nodes that minimize the maximum of all distances to the other nodes.

centerTree[t_] := 
      Module[{d, i, j, n = Length[Flatten[t]]}, 
d = 
          Table[0, {n}, {n}]; 
Do[
d[[i, 
              j]] = d[[j, 
                i]] = distance[t, i, j], {i, n - 1}, {j, 
            i + 1, n}]; 
d = 
          Max /@ d; 
Flatten[
          Position[d, First[Union[d]]]]]

centerTree[smallTree]
centerTree[bigTree1]
centerTree[bigTree2]

Note that centers are unique or adjacent.

7) DRAWING TREES

The most adequate representation of a tree structure, instead of the one the long or short notation provide, is the graphical one. This section will  aim at providing an initial function to draw trees. Two other ones will be given at the end of this work. 
Auxiliary function drT  below draws a given tree so that its root is placed at a given cartesian point (x, y). The main function drawT computes the graphical presentation of a tree. Its labels are drawn using a specific color and size. Nodes are drawn as circles in a given color and the color of the edges can also be chosen. Several examples follow.

<< "Graphics`Colors`"

\(drT[t : {r_, sT_}, {x_, y_}] := 
      Module[{w = width[t], wSons, n = Length[sT], sons, i, 
          treeGraph = {}}, 
wSons = 
          width /@ \ sT; 
sons = 
          Table[{x - w\/2, 
                y - 1} + {wSons[[i]]\/2 + Plus @@ Take[wSons, i - 1], 0}, {i, n}]; 
MapThread[
          AppendTo[
              treeGraph, {Line[{#1, {x, y}}], Disk[#1, 0.3], Circle[#1, 0.3], 
                Text[First[#2], #1]}] &, {sons, 
            sT}]; 
MapThread[
          AppendTo[treeGraph, drT[#2, #1]] &, {sons, 
            sT}]; 
Flatten[treeGraph]]
\)
\(drawT[t_, {textColor_, textSize_}, nodesColor_, edgesColor_] := 
      Module[{ts, d, dL, dD, dT, 
          dC}, 
ts = $TextStyle; 
$TextStyle = {FontFamily -> "Arial", 
            FontSize -> textSize, FontWeight -> "Bold", 
            FontColor -> textColor}; 
d = 
          drT[t, {0, 0}]; 
dL = 
          Cases[d, Line[_]]; 
dD = 
          Cases[d, Disk[_, _]]; 
dC = 
          Cases[d, Circle[_, _]]; 
dT = 
          Cases[d, 
            Text[_, _]]; 
d = {{edgesColor, 
              AbsoluteThickness[3], dL}, {nodesColor, dD, 
              Disk[{0, 0}, 0.5]}, {Black, dC, Circle[{0, 0}, 0.5]}, {dT, 
              Text[First[t], {0, 0}]}}; 
Show[
          Graphics[{d}, AspectRatio -> Automatic, 
            PlotRegion -> {{0.1, 0.9}, {0.1, 
                  0.9}}]]; 
$TextStyle = ts;]\)

drawT[smallTree, {Snow, 20}, Indigo, Firebrick];

drawT[bigTree1, {Cobalt, 12}, Floral, EnglishRed];

drawT[bigTree2, {VenetianRed, 10}, CyanWhite, 
        Chocolate];

More examples

g = {{1, 2}, {2, 3}, {3, 4}};
drawT[fromPairs[g], {Antique, 20}, LightSlateGray, 
        SlateGray];
shortNotation[fromPairs[g]]

g = {{1, 2}, {1, 3}, {1, 4}};
drawT[fromPairs[g], {AliceBlue, 20}, Salmon, 
        Melon];
shortNotation[fromPairs[g]]

g = {5, {{10, {{8, {}}}}, {3, {{11, {}}, {12, {{2, {{13, {}}, {14, {{15, {}}, {16, {}}, {17, {}}, {18, {}}}}}}}}, {7, {}}}}, {9, {{1, {}}, {6, {}}}}, {4, {}}}};
drawT[g, {Yellow, 12}, ManganeseBlue, 
        WarmGray];
shortNotation[fromPairs[toPairs[g]]]

8) RECURSIVELY GROWING TREES

Binomial trees

As an example of tree-structure specification, we take the so-called binomial trees (see section 7.2.1.3 of  Knuth´s forthcoming 4th volume of his Art of Computer Programming)

bT[0] := {1, {}}
bT[n_] := 
      Module[{i}, {1, 
          Table[bT[i], {i, 0, 
              n - 1}]}]

binomialT[n_] := 
      Module[{g = bT[n], 
          i = 1}, 
Map[(g = 
                ReplacePart[g, i, #]; i++) &, 
          Position[g, 1]]; 
g]

Note we cannot have used function rename in the definition of binomialT.

drawT[binomialT[5], {Black, 10}, ManganeseBlue, 
        UltramarineViolet];
shortNotation[binomialT[5]]

preOrder[binomialT[5]]

postOrder[binomialT[5]]

breathOrder[binomialT[5]]

Fibonnaci trees

fiboT[0] := {1, {}}
fiboT[n_] := 
      Module[{i}, {1, {bT[n - 1], 
            bT[n - 2]}}]

fibonacciT[n_] := 
      Module[{g = fiboT[n], 
          i = 1}, 
Map[(g = 
                ReplacePart[g, i, #]; i++) &, 
          Position[g, 1]]; 
g]

drawT[fibonacciT[5], {Black, 10}, ManganeseBlue, 
        UltramarineViolet];
shortNotation[fibonacciT[5]]

preOrder[fibonacciT[5]]

postOrder[fibonacciT[5]]

breathOrder[fibonacciT[5]]

Subtree embedding

Finally, inspired by the pumping lemma of context-free grammars, we design function pump that, given a tree t, nodes i and j and a set of labels, "pumps" (substitutes) the subtree with root i with the subtree with root j in which the labels are changed accordingly. This results in an easy way of growing  huge trees useful in an experimental environment.

pump[t_, i_, j_, newLabels_] := 
      t /. subTree[t, i] -> rename[subTree[t, j], newLabels]

shortNotation[smallTree]
shortNotation[pump[smallTree, 1, 5, {1, 7, 8}]]
shortNotation[pump[smallTree, 6, 5, {6, 7, 8}]]

g = longNotation["1(2,3)"];
drawT[
        Nest[(r = numNodes[#]; pump[#, r, 1, Range[r, 2  r - 1]]) &, g, 
          3], {White, 10}, ManganeseBlue, UltramarineViolet];

g = longNotation["1(2(3,4),5)"];
drawT[
        Nest[(r = numNodes[#]; pump[#, r, 1, Range[r, 2  r - 1]]) &, g, 
          3], {White, 9}, ManganeseBlue, UltramarineViolet];

Part II Generation

Of all the (2^((n^2))) relations on a set of n elements, only a small fraction are non-reflective (i.e. no element relates to itself) and symmetric, namely (2^(((n(n - 1))/2))); and of these, only (({{((n(n - 1))/2)}, {\(\(
\)\(n - 1\)\)}})) correspond to relations of size n-1, a necessary property for a tree.

n = 6;
(2^((n^2)))
(2^(((n (n - 1))/2)))
Binomial[((n (n - 1))/2), n - 1]

Of these relations, it is enough to check for connectedness to select all trees. We also face the task of filtering them further in order to obtain those non-isomorphic ones. We could eliminate matrices having at least one zero row, shortening the upper bound number. We thus arrive at the following conjeture: a necessary and sufficient condition for a non-reflective/symmetric matrix having 2(n-1) non-zero entries to be a tree is the absence of a zero-row. Whether or not this conjecture proves true, this result provides us with a useful upper bound for this number.

\(upperDiag[nodes_] := 
      Module[{m = \(nodes \((nodes - 1)\)\)\/2, d, 
          edges = nodes - 1}, 
d = 
          Map[IntegerDigits[#, 2, m] &, 
            Range[2\^m - 1]]; 
Select[
          d, \((Plus\  @@ \ # == edges)\) &]]
\)
\(symMatrix[d_] := 
      Module[{n, m, i, j, 
          k = 1}, 
n = \(1 + \@\(1 + 8\ Length[d]\)\)\/2; 
m = 
          Table[0, {n}, {n}]; 
Do[
Do[
m\_\(\([[\)\(i, j\)\(]]\)\) = \(m\_\(\([[\)\(j, i\)\(]]\)\) = 
                d\_\(\([[\)\(k\)\(]]\)\)\); \ \(k++\), \ {j, i - 1}], {i, 2, n}]; 
m]
\)
\(allNonReflSym[n_] := \(\(symMatrix\  /@ \ 
        upperDiag[n]\)\(
\)\(	\)\)\)
someZeroRowQ[m_] := 
      Position[(Plus  @@  #) &  /@  m, 
          0] ≠ {}

In order to obtain all candidates to non-isomorphic trees on, say, four nodes we proceed as follows:

MatrixForm  /@  (u = 
          Select[allNonReflSym[4], Not[someZeroRowQ[#]] &])

v = (fromMatrix[{1, #}] &  /@  u);
shortNotation /@  v

We can extract in the former those final candidates to non-isomorphic trees by disregarding labels.

shortNotation  /@  
      Union[Map[(#  /.  _Integer -> 0) &, v]]

Hence, it turns out that there are five different trees on four vertices. This procedure, however, rapidly gets computationaly too demanding. In the next part of this work we will apply a faster strategy towards the enumeration of non-isomorphic trees.

Random trees

The previous method, however, suggests a method to generate pseudo-random trees of a given number of nodes

n = 30;
m = z = Table[0, {n}, {n}];
While[
        And @@ (Positive /@ (Plus @@ m)) == 
          False, 
m = z; 
k = 
          0; 
While[
          i = Random[Integer, {1, n}]; 
j = 
            Random[Integer, {1, n}]; 
(i ≠ 
                j) && (k < n - 1), 
If[
            (Subscript[m, [[i, j]]]) == 
              0, (Subscript[m, [[i, j]]]) = (Subscript[m, [[j, i]]]) = 
                1; k++]]];
drawT[fromMatrix[{Random[Integer, {1, n}], m}], {White, 10}, 
        ManganeseBlue, UltramarineViolet];

9) NORMAL FORM

Our aim in this second part will be in generating all non-isomorphic trees of a given number of nodes. To this end we look for an invariant of trees, that is, a property that distinguishes one tree from a different one in a univocal way. Clearly, the number of nodes is not an invariant, but it helps to distinguish non-isomorphic trees in a quick manner. In addition to the number of nodes, the height of a tree cannot be an invariant because we can find pairs of isomorphic and non-isomorphic trees having the same nodes and height, namely, 1(2(3),4) and 1(2,3(4)) or 1(2(3),4) and 1(2,3,4) respectively.  Adding to these two last criteria the distintion of width helps to distinguish the last pair but not the first pair. These three qualities, although helpful in differentiating a large amount of non-isomorphic trees are not the full invariant we seek. 
Before extending this list of properties we design function liftUp, which will be instrumental in providing a fourth property to add to our invariant. This function will take a given tree t and an integer and pull the tree up so that the node corresponding to the given label will be now at the top of t which will re-shape accordingly as the following examples show.

liftUp[{r_, {sT__}}, r_] := {r, {sT}}
liftUp[t_, r_] := 
      Module[{p = toPairs[t], q, i, j}, 
q = 
          FixedPointList[
            p /. {{___, {xxk_, #}, ___} -> xxk, {___} -> 0} &, 
            r]; 
fromPairs[
          Map[({i, j} = #; If[MemberQ[q, j], {j, i}, #]) & , 
            p]]]

drawT[liftUp[smallTree, 3], {Snow, 20}, Indigo, 
        Firebrick];

An alternative way of accomplishing this is:

t = toMatrix[smallTree];
(Subscript[t, [[1]]]) = 
        3;
drawT[fromMatrix[t], {Snow, 20}, Indigo, Firebrick];

drawT[liftUp[bigTree1, 16], {Cobalt, 9}, Floral, 
        EnglishRed];

t = bigTree1;
drawT[liftUp[t, First[centerTree[t]]], {Cobalt, 9}, Floral, 
        EnglishRed];

To control the way the re-shaping of a tree takes place, we design function shake below. Shaking a tree means ordering their subtrees lexicographically on their height, width and number of nodes in such a way that the largest subtrees are placed at the left.

shake[{r_, {}}] := {r, {}}
\(shake[{r_, {sT__}}] := 
      Module[{h = \({#, height[#], width[#], 
                  numNodes[#]} &\)\  /@ \ {sT}}, 
		{r, 
          shake\  /@ \ \(First\  /@ \ 
              Sort[h, \((\((#2\_\(\([[\)\(2\)\(]]\)\) < #1\_\(\([[\)\(2\)\(]]\)\))\)\  || \ \((\((#2\_\(\([[\)\(2\)\(]]\)\) == #1\_\(\([[\)\(2\)\(]]\)\))\)\  && \ \((#2\_\(\([[\)\(3\)\(]]\)\) < #1\_\(\([[\)\(3\)\(]]\)\))\))\)\  || \ \((\((#2\_\(\([[\)\(2\)\(]]\)\) == #1\_\(\([[\)\(2\)\(]]\)\))\)\  && \ \((#2\_\(\([[\)\(3\)\(]]\)\) == #1\_\(\([[\)\(3\)\(]]\)\))\)\  && \ \((#2\_\(\([[\)\(4\)\(]]\)\) < #1\_\(\([[\)\(4\)\(]]\)\))\))\))\) &]\)}]\)

Lifting up a tree over any of its centers gives rise to trees having the same depth (the minimum possible) and width as shown below.

t = bigTree2;
drawT[
        f1 = shake[
            liftUp[t, centerTree[
                  t][[1]]]], {VenetianRed, 10}, CyanWhite, Chocolate];

t = bigTree2;
drawT[
        f2 = shake[
            liftUp[t, centerTree[
                  t][[2]]]], {VenetianRed, 10}, CyanWhite, Chocolate];

We aim to associate a unique form to a tree in such a way that two trees can be said  isomorphic iff they have the same form, which we will call normal form. The operation of lifting a tree on some of its centers, or center, and shaking leads to a good candidate for normal form. This normal form will be a useful addition to the invariant we are looking for as we simply compare normal forms to distinguish two given trees. However, in the case of the existance of two centers, the issue is how to choosse between them. In this regard consider the notion of energy (by analogy with the potential energy of an object, being the nodes of a tree regarded as unit masses) of a tree as being the sum of all distances of  the nodes to the root.

energy[t : {r_, _}] := 
      Module[{d, i, n = Length[Flatten[t]]}, 
d = 
          Table[distance[t, i, r], {i, n}]; 
Plus  @@  
          d]

energy[longNotation["1(2(3,4))"]]
energy[longNotation["1(2(3),4)"]]

energy[f1]
energy[f2]

So, we choose the center that provides minimum energy.

normalForm[t_] := 
      Module[{c = centerTree[t], t1, t2, e1, e2}, 
t1 = 
          liftUp[t, 
            c[[1]]]; 
If[
          Length[c] == 2, 
t2 = 
            liftUp[t, 
              c[[2]]]; 
e1 = energy[t1]; 
e2 = 
            energy[t2]; 
If[e1 > e2, 
            t1 = t2]]; 
shake[t1]]

drawT[normalForm[bigTree1], {Cobalt, 9}, Floral, 
        EnglishRed];

drawT[normalForm[bigTree2], {VenetianRed, 10}, CyanWhite, 
        Chocolate];

Our candidate for invariance, i.e., for normal form, will include all of the other criteria plus equality of the normal form (up to labeling). However, there is a pair of isomorphic trees having the same number of nodes, height , width and different normal form, namely 1(2(3(4,5),6(7),8) and 1(2(3(4),5),6(7(8))). 
We need to find an extra property to add to the others.  We start by designing  functions leftBranch, which computes the set of nodes comprising the leftmost path of a given tree and lexicographiQ, which tests whether two given sequences are ordered lexicographically.

leftBranch[{r_, {}}] := {r}
leftBranch[{r_, {t_, ___}}] := Flatten[{r, leftBranch[t]}]

leftBranch[bigTree2]

leftBranch[normalForm[bigTree2]]

lexicographicQ[{}, {}] := True
lexicographicQ[{a_, ___}, {b_, ___}] := False  /;  a > b
lexicographicQ[{a_, ___}, {b_, ___}] := True  /;  a < b
lexicographicQ[{a_, b___}, {c_, d___}] :=  
      lexicographicQ[{b}, {d}]

lexicographicQ[{1, 2, 3, 1}, {1, 2, 2, 1}]

lexicographicQ[{2, 2, 2, 1}, {2, 3, 2, 4}]

Function hull below selects the leftmost branches of the first two subtrees of a given tree, merge them together with the root and computes the lexicographically least sequence of associated degrees.  
For instance, the first two subtrees of  bigTree2 start at nodes 5 and 4 and their corresponding left branches are {5, 11} and {4, 9} respectively. We will always reverse the first sequence , append to the root and to the second sequence, giving in this case the total sequence of nodes 11, 5, 1, 4,  9 (for the normal formal of bigTree2 we would obtain the sequence 21, 13, 6, 2, 1, 3, 8, 17 as we can see from the drawing of it above.) Their corresponding degrees are 1, 4, 4, 2, 1. Comparing this sequence with its reverse 1, 2, 4, 4, 1 we see that the latter is lexicographically the lesser one and so, it is the one we choose to be the hull of bigTree2  (for the normal formal of bigTree2 we would obtain the sequence of degrees 1, 4, 2, 2, 4, 3, 3, 1).

hull[t : {r_, {{r1_, sT1_}, {r2_, sT2_}, ___}}] := 
      Module[{l1 = leftBranch[{r1, sT1}], l2 = leftBranch[{r2, sT2}], l, 
          d = degrees[t], d1, d2}, 
l = 
          Join[Reverse[l1], {r}, l2]; 
d1 = 
          d[[
            l]]; 
d2 = 
          Reverse[d1]; 
If[lexicographicQ[d1, d2], d1, 
          d2]]

hull[bigTree2]

Timing[hull[normalForm[smallTree]]]

Timing[hull[normalForm[bigTree1]]]

Timing[hull[normalForm[bigTree2]]]

(timing taken on a 700 MHz PC)

10) GENERATING NON-ISOMORPHIC TREES

In comparing normal forms, we disregard the labels of the final trees. However, we need them to support the tree, so instead we will provide trees with a new standard labeling using the natural order of the old labels. Procedure skin accomplishes this.

skin[t_] := 
      Module[{q = Characters[shortNotation[t]], i, 
          j = 1}, 
Do[
If[
            q[[i]] == "0", 
            q[[i]] = 
              ToString[j]; j++], {i, 
            Length[q]}]; 
longNotation[
          StringJoin[q]]]

shortNotation[bigTree1]
shortNotation[skin[bigTree1  /.  _Integer -> 0]]

Function grow below computes the family of all the trees obtained by grafting a new branch (edge) to a given tree.

grow[t : {r_, {sT__}}] := 
      Module[{n, v = Flatten[t], trees}, 
n = 
          Max[v] + 1; 
trees =  
          Map[normalForm[fromPairs[Append[toPairs[liftUp[t, #]], {n, #}]]] &, 
            v]; 
skin  /@  
          Union[trees   /.  _Integer  -> 0]]

shortNotation  /@  grow[longNotation["1(2(3),4)"]]

shortNotation  /@  grow[longNotation["1(2,3,4)"]]

Finally, function nonIsomorphicTrees computes all different trees of n nodes.

nonIsomorphicTrees[1] := {{{1, {}}, 1, 1, 0, {1}}}
nonIsomorphicTrees[2] := {{{1, {{2, {}}}}, 1, 2, 1, {1, 1}}}
nonIsomorphicTrees[n_] := nonIsomorphicTrees[n] = 
        Module[{u = First  /@  nonIsomorphicTrees[n - 1], v, w, t}, 
          v = Union[Flatten[Map[grow[#] &, u], 1]]; 
          w = Map[{#, width[#], height[#], energy[#], hull[#]} &, v];  
          w  //.  {a___, {b_, c_, d_, e_, f_}, g___, {_, c_, d_, e_, f_}, 
                h___} -> {a, {b, c, d, e, f}, g, h}]

We proceed now to show running times, trees and their properties up to 10 nodes as ran on a 700 MHz PC machine (see Sloan´s sequence 299 corresponding to Unlabeled Trees.) The format of each row is: tree, width, height, energy and hull:

\(Do[
	u = Timing[\(t = nonIsomorphicTrees[n];\)]; 
	
      Print["Computing Time: ", First[u], ". There are ", 
        Length[t], " trees of ", n, " nodes:"]; 
	
      Print[Map[Join[{shortNotation[First[#]]}, Rest[#]]\  &, t] // \ 
          MatrixForm], {n, 3, 10}]\)

We can readily display all such trees by using function drawT as follows:

t = First  /@  nonIsomorphicTrees[6];
Map[drawT[#, {VanDykeBrown, 12}, MediumTurquoise, MediumOrchid] &, 
        t];

11) BINARY TREES

Binary trees constitute one of the most important subfamilies of trees. They are characterized by the fact that any node is joined to at most two other ones. Our aim in this section is to generate all binary trees of a given height having a given number of nodes. We adopt the following notation: we use the label y to mean a leaf and label x to mean an absent edge. For instance, the notation {{x,{y,y}},x} represents the tree:

Note we cannot use function drawT introduced in part I because binary trees are oriented (i.e. the left branch is distinguished from the right one and can indeed be absent). A more familiar graphical representation, which will be used in the last part of this work is:

Enumerating

In this section we count the number of binary trees, which we will refer to simply as trees. As was the case for general rooted trees we adopt a shorter format for binary trees:

showTree[{tL_, tR_}] := "(" <> showTree[tL] <> 
        showTree[tR] <> ")"
showTree[x_] := x

showTree[{{{"y", "x"}, "x"}, "x"}]

In order to have an extended version of Outer working on lists of lists we design function myOuter below:

myOuter[list1_, list2_] := 
      Flatten[Outer[List, list1, list2, 1], 1]

myOuter[{1, 3, 2, 4}, {3, 4, 1}]

myOuter[{{1, 2}, {3, 1}}, {{1, 3}, {1, 2}}]

Given a height (depth) d, function ij generates all pairs of positive integers (i, j) such that max(i, j)=d.

ij[d_] := 
      Append[Flatten[Table[{{i, d}, {d, i}}, {i, 0, d - 1}], 1], {d, 
          d}]

ij[5]

All trees of a given height and number of nodes are obtained through the use of function binaryTrees:

binaryTrees[0, 1] := {"y"}
binaryTrees[0, _] := {}
binaryTrees[dep_, nodes_] := binaryTrees[dep, nodes] = 
        Module[{t, d = dep - 1, n = nodes - 1, case1, case2, case3 = {}, tih, 
            tjk, h, u, v}, 
t = 
            binaryTrees[d, 
              n]; 
case1 = ({#, "x"} &) /@  
              t; 
case2 = ({"x", #} &) /@  
              t; 
Map[({u, 
                    v} = #; 
Do[
tih = 
                    binaryTrees[u, h]; 
tjk = 
                    binaryTrees[v, n - h]; 
AppendTo[case3, 
                    myOuter[tih, tjk]], {h, n - 1}]) &, 
            ij[d]]; 
Join[case1, case2, 
            Flatten[case3, 1]]]

showTree  /@  binaryTrees[2, 3]

To obtain, say, all trees of height 2, we proceed as follows. Note that the number of nodes of a tree is equal to the number of x´s plus twice the number of y´s minus one.

\(Do[
	
      Print[n, "	", b = binaryTrees[2, n]; showTree /@ b, 
        Length[b]], {n, 7}]\)

The distribution corresponding to the 651 trees of height 3 is obtained as shown below. We read that, for instance, there are 20 of such trees of 5 nodes.

Table[Length[binaryTrees[3, n]], {n, (2^4) - 1}]
Plus @@ %

With the help of ij, function nT computes the number of possible  trees of a given depth.

nT[0] := 1
nT[dep_] := nT[dep] = 
        2 nT[dep - 1] + 
          Plus @@ (nT[First[#]] nT[Last[#]] &) /@  
              ij[dep - 1]

Table[nT[d], {d, 0, 6}]

The above sequence is reported as sequence 1251 corresponding to "A Nonlinear recurrence" in Sloan´s book.

Consider two trees as isomorphic if one can be obtained from the other by rotating (transposing) some of their branches. Function nTRed counts how many of them having a given depth are non-isomorphic.

nTRed[0] := 1
nTRed[dep_] := nTRed[dep] = 
        nTRed[dep - 1] (2 + (∑_(i = 0)^(dep - 2))nTRed[i] + 
              (1/2) (nTRed[dep - 1] - 1))

Table[nTRed[d], {d, 0, 6}]

The above corresponds to sequence 718 in Sloane´s book.

We are now ready to obtain the distribution of non-isomorphic trees by height and number of nodes. The accompaning example below shows those distributions up to height 4.

nTRed[0, 1] := 1
nTRed[0, _] := 0
nTRed[_, 1] := 0
nTRed[dep_, nodes_] := nTRed[dep, nodes] = 
        Module[{d = dep - 1, n = nodes - 1, s1, s2, s3, i, 
            h}, 
s1 = 
            nTRed[d, 
              n]; 
s2 = (∑_(i = 0)^(d - 1))(∑_(h = 1)^(n - 1))nTRed[i, h] nTRed[d, 
                    n - h]; 
s3 = (1/2) ((∑_(h = 1)^(n - 1))nTRed[d, h] nTRed[d, n - h] + 
                  If[OddQ[n], 0, nTRed[d, (n/2)]]); 
s1 + 
            s2 + s3]

u = Table[nTRed[d, i], {d, 4}, {i, (2^(d + 1)) - 1}];
\(Do[
	
      Print[d, "  ", 
        u[[d]], "  ", 
        Plus @@ u[[d]]], {d, 
        4}]\)

Generating

We now generate all the trees counted in the previous section. We begin by specializing function Outer:

myOuter2[singleList_] := 
      Union[Sort  /@  myOuter[singleList, singleList]]

myOuter2[{1, 2, 3}]

myOuter2[{{1, 2}, {3, 1}}]

Similarly as when enumerating the non-isomorphic trees at section 10, three cases arise in generating them. Function binTreesRed sets up the stage using the previous functions.

\(binTreesRed[dep_, nodes_] := \(\({}\  /; \ 
        Not[dep < nodes < 2\^\(dep + 1\)]\)\(
\)\(	\)\)\)
\(\(binTreesRed[0, 1] = {"y"};\)
\)
\(binTreesRed[dep_, nodes_] := \(binTreesRed[dep, nodes] = 
        Module[{case1, case2 = \(case3 = \(case4 = {}\)\), i, h, ih, tih, 
            tOther, lim}, 
case1 = 
            Map[{#, "x"} &, 
              binTreesRed[dep - 1, nodes - 1]]; 
ih = 
            myOuter[Range[0, dep - 2], 
              Range[nodes - 2]]; 
ih = 
            Select[ih, \((Max[First[#], nodes - 2\^dep - 1] < Last[#] < 
                    Min[nodes - dep, 
                      2\^\(First[#] + 1\)])\) &]; 
Map[\(({i, h} = #; 
tih = 
                  binTreesRed[i, h]; 
tOther = 
                  binTreesRed[dep - 1, 
                    nodes - 1 - h]; 
AppendTo[case2, 
                  myOuter[tih, tOther]])\) &, ih]; 
case2 = 
            Flatten[case2, 
              1]; 

lim = \(nodes - 1\)\/2; 
If[OddQ[nodes], 
            lim = lim - 1]; 
ih = 
            myOuter[{dep - 1}, Range[lim]]; 
ih = 
            Select[ih, \((Max[dep - 1, nodes - 2\^dep - 1] < Last[#] < 
                    Min[nodes - dep, 
                      2\^dep])\) &]; 
Map[\(({i, 
                    h} = #; 
tih = 
                  binTreesRed[i, h]; 
tOther = 
                  binTreesRed[dep - 1, 
                    nodes - 1 - h]; 
AppendTo[case3, 
                  myOuter[tih, tOther]])\) &, ih]; 
case3 = 
            Flatten[case3, 1]; 

If[
            OddQ[nodes], 
tih = 
              binTreesRed[dep - 1, lim + 1]; 
AppendTo[
              case4, myOuter2[tih]]; 
case4 = 
              Flatten[case4, 1]]; 
			
Join[case1, 
            case2, case3, case4]]\)\)

For instance, to obtain all different trees of height 1 and at most 4 nodes:

Table[showTree  /@  binTreesRed[1, n], {n, 4}]

and to obtain all different trees of 5 nodes and height 3:

showTree  /@  binTreesRed[3, 5]

The complete distribution of non-isomorphic trees of height 2 is:

h = 2;
\(Do[
	
      Print[n, "	", bt = binTreesRed[h, n]; showTree /@ bt, "	", 
        Length[bt]], {n, h + 1, 2\^\(h + 1\) - 1}]\)

The length of binTreesRed[h, n] is non-zero only in the range h < n < (2^(h + 1)). There is only one reduced tree when n ∈ {h+1, (2^(h + 1))-1}.

First alternative drawing

We now offer the first of two different ways of drawing binary trees. Given a list of Lines and a point v, function addLines translates all lines an amount v as shown in the example following the code.

addLines[li_, v_] := 
      Module[{u = li /. Line[l_] -> l, 
          h}, (Line[#] &) /@ ((h = #; (# + v &) /@ h) &) /@ 
            u]

addLines[{Line[{{1, 2}, {3, 4}}], 
        Line[{{0, 0}, {0, 1}, {-1, -1}}]}, {1, 2}]

The following function treeShape computes an orthogonal version of the graphical representation of a tree as the example shows.

treeShape["x"] := {1, 1, 0, {}}
treeShape["y"] := {1, 1, 0, {Line[{{1, 0}, {1, 1}}]}}
\(treeShape[{tL_, tR_}] := 
      Module[{h, a, b, L, k, c, d, R, ahk, hp, ap, bp, ans, 
          delta = 1}, 
{h, a, b, L} = 
          treeShape[tL]; 
{k, c, d, R} = 
          treeShape[tR]; 
ahk = 
          If[h > k, 0, Abs[h - k]]; 
hp = 
          Max[h, k] + 1; 
ap = 
          a + \(\((c + d)\)\ \((delta\ \((a + b + c + d)\) - a - d)\)\)\/\(a + b + c + d\); 
        bp = delta\ \((a + b + c + d)\) - ap; 
ans = 
          addLines[L, {0, ahk}]; 
AppendTo[
          ans, {Line[{{a, h + ahk}, {ap + bp - d, h + ahk}}], 
            Line[{{ap, h + ahk}, {ap, h + ahk + 1}}]}]; 
        AppendTo[ans, addLines[R, {ap + bp - c - d, h + ahk - k}]]; {hp, ap, 
          bp, Flatten[ans]}]
\)
drawTree[t_] := 
      Module[{u = Last[treeShape[t]]}, 
        Show[Graphics[u], AspectRatio -> Automatic]]

drawTree[{{{"y", "x"}, "x"}, "x"}];

By using the above, we can generate a graphic array containing all different trees of a given height:

drawAllTrees[trees_, nColumns_] := 
      Module[{u, 
          n = Length[
              trees]}, 
u = (Graphics[
                  Last[treeShape[#]]] &) /@ trees; 
u = 
          Join[u, Table[
              Graphics[
                Point[{0, 0}]], {nColumns Ceiling[(n/nColumns)] - 
                  n}]]; 
Show[
          GraphicsArray[Partition[u, nColumns]], 
          AspectRatio -> Automatic]]

k = 2;
t = 
        Flatten[Table[binaryTrees[k, n], {n, k + 1, (2^(k + 1)) - 1}], 
          1];
drawAllTrees[t, 5];

Second alternative drawing

An alternative graphical representation is that one using oblique lines to connect nodes. This representation is provided by function treeShape2 below and used to generate the corresponding  graphic array in function drawAllTrees2.

treeShape2["x"] := {1, 1, 0, {}}
treeShape2["y"] := {1, 1, 0, {Line[{{1, 0}, {1, 1}}]}}
\(treeShape2[{tL_, tR_}] := 
      Module[{h, a, b, L, k, c, d, R, ahk, hp, ap, bp, ans, 
          delta = 1}, 
{h, a, b, L} = 
          treeShape2[tL]; 
{k, c, d, R} = 
          treeShape2[tR]; 
ahk = 
          If[h > k, 0, k - h]; 
hp = 
          Max[h, k] + 1; 
ap = 
          a + \(\((c + d)\)\ \((delta\ \((a + b + c + d)\) - a - d)\)\)\/\(a + b + c + d\); 
bp = 
          delta\ \((a + b + c + d)\) - ap; 
ans = 
          addLines[L, {0, ahk}]; 
AppendTo[
          ans, {Line[{{a, h + ahk}, {ap, h + ahk + 1}, {ap + bp - d, 
                  h + ahk}}]}]; 
        AppendTo[ans, addLines[R, {ap + bp - c - d, h + ahk - k}]]; {hp, ap, 
          bp, Flatten[ans]}]
\)
drawAllTrees2[trees_, nColumns_] := 
      Module[{u, 
          n = Length[
              trees]}, 
u = (Graphics[
                  Last[treeShape2[#]]] &) /@ trees; 
u = 
          Join[u, Table[
              Graphics[
                Point[{0, 0}]], {nColumns Ceiling[(n/nColumns)] - 
                  n}]]; 
Show[
          GraphicsArray[Partition[u, nColumns]], 
          AspectRatio -> Automatic]]

In the following we show the number of non-isomorphic trees with depth 1, 2 and 3. (For the generation of non-isomorphic trees of depth d, generate the previous cases of depth d-1, d-2,...,2,1; this, in virtue of the recursive procedure and because of the use of function binTreesRed that remembers the values it has found).

d = 1;
t = 
        Flatten[Table[binTreesRed[d, n], {n, d + 1, (2^(d + 1)) - 1}], 
          1];
drawAllTrees2[t, 5];
Length[t]

d = 2;
t = 
        Flatten[Table[binTreesRed[d, n], {n, d + 1, (2^(d + 1)) - 1}], 
          1];
drawAllTrees2[t, 5];
Length[t]

d = 3;
t = 
        Flatten[Table[binTreesRed[d, n], {n, d + 1, (2^(d + 1)) - 1}], 
          1];
drawAllTrees2[t, 14];
Length[t]

REFERENCES:

A Handbook of Integer Sequences			   Enumerative Combinatorics Vol. 2
N.J.A. Sloane							R.P. Stanley
Academic Press						Cambridge University Press

The Art of Computer Programming			  Applied Combinatorics
Vol. 1 Fundamental Algorithms			  F. S. Roberts
D.E. Knuth						           Prentice Hall
Addison-Wesley