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

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.

• $T(1)$ is infinite because every linear binary tree has one leaf. May 6, 2021 at 0:16

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$$.

• Also these are the Catalan numbers: en.wikipedia.org/wiki/Catalan_number May 5, 2021 at 23:52
• Wont u get a tree with $n$ leaves by combing a tree with $k-1$ and $n-k$ leaves because when u combine 2 trees u r removing one of the leaves of original tree.. ? May 6, 2021 at 2:22

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;
}