Number of Binary Trees
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 :
- 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 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.
- 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 such trees. Therefore the total number of such tress are .
- 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 such trees. Therefore the total number of such tress are .
Hence we get the recurrent relation
or
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 :
- The total number of binary trees with n nodes is , also known as Catalan numbers or Segner numbers.
- tn,n = 2n-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? 🙂
Philip
April 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]
celicom
May 16, 2011 at 1:14 AM
Hi
is there any solution to solve this problem with O(nh) ?
thanks
Simin
November 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?
yogendra
August 8, 2015 at 3:50 PM