# Unique Binary Search Trees

## Recursion

I solve this prolem in the toilet.

### Review building a BST

```
function buildBST(nodes, root)
root.left = buildBST(nodes that their vals are less than root.val)
root.right = buildBST(nodes that their vals are greater than or equal to root.val)
```

change to numbers.

```
function numTrees(nodes, root)
return numTrees(nodes that their vals are less than root.val) * numTrees(nodes that their vals are greater than or equal to root.val)
```

that is, there are `numTrees`

on `root.left`

and `numTrees`

on `root.right`

, so in sum just `left`

times `right`

.

### How many roots

Any number can become the root, so just add them up.

```
foreach node in nodes
sum = sum + numTrees(nodes, node)
```

## Empty tree

let `numTrees(empty tree) = 1`

. codes will go well.

### Source code *Read on Github*

```
1 public class Solution {
2 public int numTrees(int n) {
3 // Note: The Solution object is instantiated only once and is reused by each test case.
4
5 if(n == 0) return 1;
6
7 int s = 0;
8
9 for(int i = 0; i < n; i++){
10 s += numTrees(i) * numTrees(n - 1 - i);
11 }
12
13 return s;
14 }
15 }
```