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

**Example:**

Input:3Output:5Explanation:Givenn= 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]; } }