$T_{n}$ a set of all binary trees with $n$ leaves

Question

Let $T_{n}$ be a set of all binary trees with $n$ leaves.

Show that: $$|T_1|=1,|T_2|=1,|T_3|=2,|T_4|=5$$

---

My attempt:

I was trying to find how many options of leaves we should add to the previous tree when the tree belongs to $T_{n-1}$, and then subtract the common options after the addition of the leaf. For example, for $T_4$ we have the following trees of $T_3$:

                     C             C  
                   /   \          / \
                  C     L        L   C 
                 / \                / \
                L   L     ,        L   L

we have 3 options to add another leaf for each tree, however, we have to remove the common tree when:

                        C       
                      /   \    
                     C     C  
                    / \   / \       
                   L   L L   L  

and we got $6-1=5$ options of trees for $T_4$.

---

Now, I don't know how to formal this and create a regression formula based on the process which I have used.

Answer 1

There is only one tree which has exactly one leaf - the tree which doesn't branch. Thus, $|T_1| = 1$.

Now consider $T_n$ for $n > 1$. A tree with $n$ leaves can only be made by combining a tree with $k$ leaves with a tree with $n - k$ leaves, where $1 \leq k < n$. That is, $T_n \approx \coprod\limits_{k = 1}^{n - 1} T_k \times T_{n - k}$. So we have $|T_n| = \sum\limits_{k = 1}^{n - 1} |T_k| \times |T_{n - k}|$.

This gives us $|T_2| = |T_1| |T_1| = 1$, $|T_3| = |T_1| |T_2| + |T_2| |T_1| = 2$, and $|T_4| = |T_1| |T_3| + |T_2| |T_2| + |T_3| |T_1| = 5$.

Answer 2

Here is the C++ code (C++11 NOT required) to visualize these trees. For large $n \geq 16$, the heap might explode.

#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <assert.h>
using namespace std;


int n = 15; //number of leaves


string int2string(int k)
{
    //std::to_string() only works >= C++11
    string s;
    stringstream ss;
    ss << k;
    ss >> s;
    return s;
}


typedef struct node
{
    bool isleaf;
    string* data; //Using string* is better. The compiler knows how to allocate memory.
    struct node* l; //left pointer
    struct node* r; //right pointer
}node;


vector<node*> recursively_constuct_trees(vector<node*>& leaves, int lower_bound, int upper_bound)
{
      //returning vector by value is a good idea due to named return value optimization (NRVO)
      vector<node*> results;
      if(lower_bound == upper_bound)
      {
          //only one node
          results.push_back(leaves[lower_bound]);
          return results;
      }
      for(int i = lower_bound; i < upper_bound; ++i)
      {
          vector<node*> results_left = recursively_constuct_trees(leaves, lower_bound, i);
          vector<node*> results_right = recursively_constuct_trees(leaves, i+1, upper_bound);
          //Catalan Convolution
          for(unsigned j = 0; j < results_left.size(); ++j)
              for(unsigned k = 0; k < results_right.size(); ++k)
              {
                  node* newnode = new node;
                  newnode -> l = results_left[j];
                  newnode -> r = results_right[k];
                  newnode -> data = new string("(" + *(results_left[j] -> data) + "+" + *(results_right[k] -> data) + ")");
                  newnode -> isleaf = false;
                  results.push_back(newnode);
              }
      }
      return results;
}

void recursively_destroy_tree(node* &root){
     if(!root || root -> isleaf) //Do not free leaves!
         return;
     recursively_destroy_tree(root -> l);
     recursively_destroy_tree(root -> r);
     delete root;
     root = NULL;
}


int main(void)
{
    assert(n >= 1);
    vector<node*> leaves;
    for(int i = 0; i < n; ++i)
    {
        leaves.push_back(new node);
        leaves[i] -> data = new string(int2string(i));
        leaves[i] -> l = NULL;
        leaves[i] -> r = NULL;
        leaves[i] -> isleaf = true;
    }
    vector<node*> result = recursively_constuct_trees(leaves, 0, n-1);
    printf("T(%d) = %d\n", n, result.size());
    for(unsigned i = 0; i < result.size(); ++i){
        cout << "VISUALIZATION (" << i <<"): " << *(result[i] -> data) << endl;
        recursively_destroy_tree(result[i]);
    }
    return 0;
}