Number of binary trees for n nodes

• Question : What is the number of rooted plane binary trees with n nodes and height h?

Solution :
Let t_n,h denote the number of binary trees with n nodes and height h.

Lets take a binary search tree of n nodes with height equal to h. Let the number written at its root be the m^thnumber in sorted order, 1 ≤ m ≤ n. Therefore, the left subtree is a binary search tree on m-1 nodes, and the right subtree is a binary search tree on n-m nodes. The maximum height of the left and the right subtrees must be equal to h-1. Now there are two cases :

1. The height of left subtree is h-1 and the height of right subtree is less than equal to h-1 i.e from 0 to h-1.
2. The height of right subtree is h-1 and the height of left subtree is less than equal to h-2 i.e from 0 to h-2, since we have considered the case when the left and right subtrees have the same height h-1 in case 1.

Therefore t_n,h is equal to the sum of number of trees in case 1 and case 2. Let’s find the number of trees in case 1 and case 2.

1. The height of the left subtree is equal to h-1. There are t_m-1,h-1 such trees. The right subtree can have any height from 0 to h-1, so there are such trees. Therefore the total number of such tress are .
2. The height of the right subtree is equal to h-1. There are t_n-m,h-1 such trees. The left subtree can have any height from 0 to h-2, so there are such trees. Therefore the total number of such tress are .

Hence we get the recurrent relation

or

where t_0,0=1 and t_0,i=t_i,0=0 for i>0.
Here’s a sample C++ code.

#include

using namespace std;

#define MAXN 35

int main()

{

long long t[MAXN+1][MAXN+1]={0},n,h,m,i;

t[0][0]=1;

for (n=1;n<=MAXN;n++)

for (h=1;h<=n;h++)

for (m=1;m<=n;m++)

{

for (i=0;i < class="line alt1"> t[n][h]+=t[m-1][h-1]*t[n-m][i];

for (i=0;i < class="line alt1"> t[n][h]+=t[n-m][h-1]*t[m-1][i];

}

while (scanf("%lld%lld",&n,&h))

printf("%lld\n",t[n][h]);

}

Note :

1. The total number of binary trees with n nodes is , also known as Catalan numbers or Segner numbers.
2. t_n,n = 2^n-1.
3. The number of trees with height not lower than h is .
4. There are other recurrence relation as well such as
   .