# [LeetCode 96] Unique Binary Search Trees

### Question

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example,
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
```

### Stats

 Frequency 1 Difficulty 3 Adjusted Difficulty 3 Time to use --------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

### Analysis

This seems like an easy recursion question, however it will result in many repeated recursion calls.

To avoid repeated recursion, use Dynamic Programming.

### Solution

First code below is my solution. It is a standard recursion solution, but it’s not good. The run time is 30ms more than next code.

Second code is DP solution, where the previous answers are saved and used forfuture calculation. This is the best solution for this question, and I learnt it from this blog.

### Code

First code

``````public int numTrees(int n) {
if (n <= 1) return 1;

int total = 0;
if (n % 2 == 0){
for (int i = 0; i <= n / 2 - 1; i ++ ){
// i is all the possible number of nodes on the left
total += 2 * numTrees(i) * numTrees(n-i-1);
}
} else {
for (int i = 0; i <= (n-1) / 2 - 1; i ++ ){
// i is all the possible number of nodes on the left
total += 2 * numTrees(i) * numTrees(n-i-1);
}
total += Math.pow(numTrees((n-1)/2), 2);
}
}
``````

Second code

``````public int numTrees(int n) {
int[] table = new int[n + 1];
table[0] = 1;
table[1] = 1;
for (int i = 2; i <= n; i++) {
int sum = 0;
for (int j = 1; j <= i; j++) {
int left = j - 1;
int right = i - j;
sum += table[left] * table[right];
}
table[i] = sum;
}
return table[n];
}
``````