# Unique BST's

Given an integer. Find how many structurally unique binary search trees are there that stores the values from 1 to that integer (inclusive).

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```

You don't need to read input or print anything. Your task is to complete the function numTrees() which takes the integer N as input and returns the total number of Binary Search Trees possible with keys [1.....N] inclusive. Since the answer can be very large, return the answer modulo 1e9 + 7.

Expected Time Complexity: O(N2).
Expected Auxiliary Space: O(N).

Constraints:
1<=N<=1000

class Solution
{
public:
const int mod=1e9+7;
//Function to return the total number of possible unique BST.
int numTrees(int n)
{
if(n==0 || n==1)return 1;
vector<long long int>dp(n+1,0);
dp=1;
dp=1;
for(int i=2; i<=n; i++){
int l=0;
int r=i-1;
while(l<=i-1){
dp[i]+=(dp[l]*dp[r])%mod;
l++;
r--;
}
dp[i]%=mod;
}
return (int)dp[n];
}
};

Explanation-

Let's start by trying to solve the problem in Brute-Force manner. To form structurally unique BST consisting of `n` nodes, we can start by taking any of the node `1...n` as the root node. Let the chosen root node be `i`. Then, we have a BST where the root node is `i`, the left child consist of all nodes from `1...i-1` (since left sub-tree must have only less than root's value) and right child consist of all nodes from `i+1...n`.

``````
1            1                   2                    3               3
\            \                 / \                  /               /
3             2              1   3                2               1
/               \                                 /                 \
2                 3                              1                    2
i = 1                   i = 2                       i = 3
(i = root node)
``````

Now, we need to realize that the number of structurally unique BST formable with nodes having value `i+1...n` is equal to the number of structurally unique BST formable with nodes having value `i+1-i...n-i = 1...n-i`. Why? Because we only need to find BST which are structurally unique irrespective of their values and we can form an equal number of them with nodes from `1...n` or `2...n+1` or `n...2n-1` and so on. So, the number only depends on number of nodes using which BST is to be formed.

Now, when we choose `i` as root node, we will have nodes from `1...i-1` (`i-1` nodes in total) in left sub-tree and nodes from `i+1...n` (`n-i` nodes in total) in the right side. We can then form `numTrees(i-1)` BSTs for left sub-tree and `numTrees(n-i)` BSTs for the right sub-tree. The total number of structurally unique BSTs formed having root `i` will be equal to product of these two, i.e, `numTrees(i-1) * numTrees(n-i)`. The same can be followed recursively till we reach base case - `numTrees(0) = numTrees(1) = 1` because we can form only a single empty BST and single node BST in these cases respectively.

The final answer will be summation of answers considering all `1...n` as root nodes.