Unique Binary Search Trees : Catalan Numbers

Count no of BST’s that can be formed using N nodes numbered from 1,2,3,….n.

Example:

Input: 3
Output: 5
Explanation:
Given n = 3, there are a total of 5 unique BST's:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Solution

Explanation

Basic Knowledge - Catalan Number

1, 2, 3, .................i...................N

      i
     / \      
  i-1   n-i

         Root
         / \      
   
 LeftSBT     RightSBT


Formula:
f(N) = Summation Of (i = 1 to N)  f(i-1) * f(N - i) 

Base cases: 
f(0) = 1;
f(1) = 1;

f(2) = Summation of (i = 1 to 2) 
At i = 1, ==> f(1-1) * f(2-1) ==> f(0) * f(1) ==> 1
At i = 2, ==> f(2-1) * f(2-2) ==> f(1) * f(0) ==> 1
Summation of (i=1 to 2) is 1 + 1 = 2;
f(2) = 2;

f(3) = Summation of (i=1 to 3)
At i = 1, ==> f(1-1) * f(3-1) ==> f(0) * f(2) ==> 2
At i = 2, ==> f(2-1) * f(3-2) ==> f(1) * f(1) ==> 1
At i = 3, ==> f(3-1) * f(3-3) ==> f(2) * f(0) ==> 2
Summation of (i=1 to 3) is 2 + 1 + 2 = 5;
f(3) = 5;

Program to understand Better

class Solution {
    public int numTrees(int N) {
        
        int[] dp = new int[N+1];
        dp[0] = 1;
        dp[1] = 1;
        
        for(int n=2;n<=N;n++)
        {
            for(int i=1;i<=n;i++)
            {
                dp[n] += dp[i-1] * dp[n-i];
            }
        }
        
        
        return dp[N];
    }
}

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s