# 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];
}
}
```