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


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: