## Number of Binary Trees

**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*^{th}number 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 :

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

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

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

.

NJOY!

-fR0DDY

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

PhilipApril 29, 2010 at 7:37 PM

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]

celicomMay 16, 2011 at 1:14 AM

Hi

is there any solution to solve this problem with O(nh) ?

thanks

SiminNovember 29, 2012 at 1:33 AM

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

yogendraAugust 8, 2015 at 3:50 PM