6
$\begingroup$

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.

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

2 Answers 2

3
$\begingroup$

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

$\endgroup$
2
  • 2
    $\begingroup$ Also these are the Catalan numbers: en.wikipedia.org/wiki/Catalan_number $\endgroup$
    – subrosar
    May 5, 2021 at 23:52
  • 1
    $\begingroup$ 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.. ? $\endgroup$
    – Balaji sb
    May 6, 2021 at 2:22
0
$\begingroup$

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;
}
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.