### 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);
}
return total;
}
```

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