# 96. Unique Binary Search Trees (Medium)

https://leetcode.com/problems/unique-binary-search-trees/

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

Example:

```Input: 3
Output: 5
Explanation:
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
```

## Solutions

``````class Solution {

// key is the quantity of nodes, value is the possible situations of unique BSTs.
private Map<Integer, Integer> situations = new HashMap<>();

public int numTrees(int n) {
// for n nodes, possible situations:
// 1. left 0 nodes, right n-1 nodes
// 2. left 1 nodes, right n-2 nodes
// ...
// i+1. left i nodes, right n-i-1 nodes
// ...
// n. left n-1 nodes, right 0 nodes

if (n <= 1) {
return 1;
}

if (n == 2) {
return 2;
}

if (situations.containsKey(n)) {
return situations.get(n);
}

int ans = 0;
for (int i = 0; i < n; i++) {
int left = numTrees(i);
int right = numTrees(n - i - 1);

ans += left * right;
}

situations.put(n, ans);

return ans;
}
}
``````