Unique BST's

 Given an integer N, Find the total number of unique binary search trees that can be made using values from 1 to N.

Example 1:

Input:
N = 2
Output: 2
Explanation:for N = 2, there are 2 unique
BSTs
     1               2  
      \            /
       2         1

Example 2:

Input:
N = 3
Output: 5
Explanation: for N = 3, there are 5
possible BSTs
  1           3     3       2     1
    \        /     /      /  \     \
     3      2     1      1    3     2
    /      /       \                 \
   2      1         2                 3

 

 Since the answer can be very large, return the answer modulo 1000000007.

c++ implementation:

int numTrees(int n) 
    {
        long long t[n+1];
        fill_n(t, n + 1, 0);
        t[0]=1;
        t[1]=1;
        
        for(int i=2;i<=n;i++)
        for(int j=0;j<i;j++)
        t[i]=(t[i]+(t[j]*t[i-j-1]))%1000000007;
        
        return t[n];
    }

Time Complexity: O(n^2) 

space Complexity: O(n)