```
def n_trees(n):
# bottom up iterative computation, 7000% faster than recursive
#
# O(n^2) time?
memo = {0: 1, 1: 1}
for k in xrange(2, n+1):
m, j = 0, 0
while j <= k-j-1:
l = memo[j]
r = memo[k-j-1]
p = l*r
if j != k-j-1:
p *= 2
m += p
j += 1
memo[k] = m
return memo[n]
```