# COME ON CODE ON

A blog about programming and more programming.

## Number of Binary Trees

with 4 comments

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

Solution :
Let tn,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 mthnumber 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 tn,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 tm-1,h-1 such trees. The right subtree can have any height from 0 to h-1, so there are $\displaystyle\sum_{i=0}^{h-1}t_{n-m,i}$ such trees. Therefore the total number of such tress are $t_{m-1,h-1}\displaystyle\sum_{i=0}^{h-1}t_{n-m,i}$.
2. The height of the right subtree is equal to h-1. There are tn-m,h-1 such trees. The left subtree can have any height from 0 to h-2, so there are $\displaystyle\sum_{i=0}^{h-2}t_{m-1,i}$ such trees. Therefore the total number of such tress are $t_{n-m,h-1}\displaystyle\sum_{i=0}^{h-2}t_{m-1,i}$.

Hence we get the recurrent relation
$t_{n,h}= \displaystyle\sum_{m=1}^{n}{(t_{m-1,h-1}\displaystyle\sum_{i=0}^{h-1}t_{n-m,i})} + \displaystyle\sum_{m=1}^{n}{(t_{n-m,h-1}\displaystyle\sum_{i=0}^{h-2}t_{m-1,i})}$
or
$t_{n,h}= \displaystyle\sum_{m=1}^{n}{(t_{m-1,h-1}\displaystyle\sum_{i=0}^{h-1}t_{n-m,i} + t_{n-m,h-1}\displaystyle\sum_{i=0}^{h-2}t_{m-1,i})}$
where t0,0=1 and t0,i=ti,0=0 for i>0.
Here’s a sample C++ code.

#include<iostream>
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<h;i++)
t[n][h]+=t[m-1][h-1]*t[n-m][i];

for (i=0;i<h-1;i++)
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 $\frac{2n!}{n!(n+1)!}$, also known as Catalan numbers or Segner numbers.
2. tn,n = 2n-1.
3. The number of trees with height not lower than h is $\displaystyle\sum_{i=h}^{n}{t_{n,i}}$.
4. There are other recurrence relation as well such as
$t_{n,h}= \displaystyle\sum_{i=0}^{h-1}{(t_{n-1,h-1-i}(2*\displaystyle\sum_{j=0}^{n-2}t_{j,i} + t_{n-1,i}))}$.

NJOY!
-fR0DDY

Advertisements

Written by fR0DDY

April 13, 2010 at 11:44 AM

Posted in Algorithm, Maths, Programming

Tagged with , , , , ,

### 4 Responses

Subscribe to comments with RSS.

1. What is a “plane” binary tree? As opposed to “beautiful” binary trees? 🙂

Philip

April 29, 2010 at 7:37 PM

2. How about getting analytical expression for t(n,h) through the generation function of two variables? 🙂
G(x,y) = sum(i,j)[t(i,j)*x^i*y^j]

celicom

May 16, 2011 at 1:14 AM

3. Hi
is there any solution to solve this problem with O(nh) ?
thanks

Simin

November 29, 2012 at 1:33 AM

4. What is the number of rooted plane binary trees with n nodes and height less than or equal to h?

yogendra

August 8, 2015 at 3:50 PM