We can go one step deeper by looking at binary trees that have 4 vertices. All 14 possible binary trees with 4 vertices are shown above. However, there are only 3 structurally different variations. Trees1, 2, 4, 5, 10, 11, 13, and 14 share a common structure. Trees 3 and 12 have a second structure. Finally, trees 6, 7, 8, and 9 share a third structure. Note that any tree within a given structure can be converted into any other tree within the same structure group by combinations of various "flips" (mirror images) of the subtrees at the appropriate vertices.

   At this point we might wonder how many possible binary trees exit for any given "N" vertices, and how many of these are structurally different. We will give the results first and then outline the algorithms showing how the data is calculated. (Note: we have included a "0" vertex row as this will be used in the calculation algorithms.)

Method 1)  If we know how many different binary trees exist up through "N" vertices, then we can calculate the number at "N + 1" via the following observations. We start by putting the "N + 1"th vertex at the root (top). Then we note that all binary trees that have "N" vertices could be tacked on to the left branch from this new vertex. We could add to this all binary trees that have "N - 1" vertices tacked to the left branch of the root combined with all trees that have 1 vertex tacked to the right branch. Continuing, we add to our total all binary trees that have "N - 2" vertices tacked to the left branch combined with all binary trees that have 2 vertices tacked to the right. We continue this process through "0" vertices tacked to the left branch and "N" vertex trees tacked to the right branch. If we use this algorithm to find the "Number of Binary Trees" for N = 8 we get: 429*1 + 132*1 + 42*2 + 14*5 + 5*14 + 2*42 + 1*132 + 1*429 = 1,430. (Check the above table to verify the source of these numbers.

Method 2)  There is a direct equation although this quickly runs into precision errors.
Number of Binary Trees[n] = COMBIN(2n, n) / (n + 1)
This can be extended to enumerate all “t-ary” trees via:
Number of t-ary Trees[n] = COMBIN(tn + 1, n) / (tn + 1) 

Method 3)  First we note that the coefficients (1, 1, 2, 5, 14, 42, etc.) form a Catalan Sequence. This can be derived from a modified Pascal's Triangle of binomial coefficients.

                 1
            1 |     1
              |  1     1
            1 |     2     1
              |  2     3     1
            2 |     5     4     1
              |  5     9     5     1
            5 |    14    14     6     1
              | 14    28    20     7     1
           14 |    42    48    27     8     1

   Each number in the table is the sum of the numbers that appear to the left and right immediately above it with the following exception. At the vertical line, the upper left number does not contribute its portion. The numbers to the left of the vertical line produce the desired coefficients.

Method 4)  There is a simple step for producing Catalan Numbers. This is illustrated below.

Index    Catalan
Number   Number
----------------
   1         1
   2         1
   3         2
   4         5
   5        14
   N        C[N-1]*(4N-6)/N

The index is off by one but this can be easily adjusted in a computer program.     




   When we calculate the number of structurally different trees, we have to define a system to differentiate between different trees that have the same structure. Thus at each vertex in the tree, we will place the subtree that has the greatest number of vertices on the left branch, and put the subtree with the smaller number of vertices on the right. If both subtrees have the same number of vertices, we arbitrarily assign a letter (A, B, C, etc.) to each different subtree structure. Then we keep the letters in alphabetical order.

   The "Number of Structurally Different Binary Trees" can be calculated easily using Method 1) from above. If we imagine the column on the right as the contents of an array, then A[N] equals the value of the array at position "N". For example A[9] = 98. If we want to calculate  A[10] given we have all the values up to A[9], then we form products using the first half of the Method 1) algorithm above. Thus, we calculate:  98*1 + 46* 1 + 23*1 + 11*2 + 6*3 = 207. In general if "N + 1" is even, then A[N+1] = A[N]*A[0] + A[N-1]*A[1] + A[N-2]*A[2] etc. and then stop before the two references cross.

   If "N+1" is an odd number, there is a slight complication, as the two references will exactly meet in the middle. Let's calculate A[11] to see the difference. The first part of the calculation is the same. We start at the two ends and work toward the middle until we get to the middle. Thus we have:  207*1 + 98*1 + 46*1 + 23*2 + 11*3 = 430. Then the two converging indexes meet at A[5] = 6.

   The 6 indicates that our new "root" node will have one of the 6 structurally different subtrees attached to its left branch, and another of the 6 possible subtrees attached to the right branch. Let's designate these 6 structurally different subtrees with the letters A, B, C, D, E, and F.

   If "A" goes on the left branch, then the right branch could have and A, B, C, D, E, or F for 6 combinations. If "B" goes on the left branch, then the right branch could get a B, C, D, E, or F for 5 more combinations. ("A" can't go on the right branch, as that would violate our alphabetical order). If "C" goes on the left, there are 4 more possible combinations. D, E, and F similarly produce 3, 2, and 1 more combinations. Thus if the contents of A[midpoint] is 6, then there are 6 + 5 + 4 + 3 + 2 + 1 = 21 combinations. If we add this 21 to the previous 430, we get 451 which is the correct value for A[11].

   In general, if we are calculating A[N], we form the vector product down to where the two indexes are about to meet. If N is even this completes the process. If N is odd, then the two indexes will meet at a midpoint. We then take the array value at this midpoint and form the sum of all integers from here down to 1. (If the value at the midpoint is "X", then sum X + (X-1) + (X-2)...+ 1 = X(X+1)/2). Finally add this amount to the prior vector product. 


Return to Durango Bill's Home Page


Web page generated via KompoZer