**Solution**

**Unique Binary Search Trees** https://leetcode.com/problems/unique-binary-search-trees/

- For a tree with nodes 1...n, the root can be 1 or 2 or 3 or 4....n
- For root say 6, we can have left subtree 1 to 5 and right subtree with 6 to n
- Total trees will be left * right

```
from collections import defaultdict
class Solution(object):
def numTrees(self, n):
"""
:type n: int
:rtype: int
"""
cache = defaultdict(int)
cache[0], cache[1], cache[2] = 1, 1, 2
for i in range(3,n+1):
for j in range(i+1):
lt, rt = cache[j], cache[i-j-1]
cache[i] += lt*rt
return cache[n]
```