Unique Binary Search Trees

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

Read more about Catalan_number on Wikipedia and this great Chinese post.

# Solution

means the nth Catalna number.

The first Catalan numbers for are: ...

The number of structurally unique BST's that store values ... is .

# Catalan Number

All following solutions use some formula to calculate nth Catalan number.

# Recursive Formula 1 (squared time)

def numTrees(self, n: int) -> int:
    C = [0]*(n+1)
    C[0] = C[1] = 1
    for i in range(2,n+1):
        for j in range(1,i+1):
            C[i] += C[j-1]*C[i-j]
    return C[n]

# Recursive Formula 2 (linear time)

def numTrees(self, n: int) -> int:
    C = 1
    for i in range(1, n+1):
        C = C * 2*(2*i-1)//(i+1)
    return C

# Binomial Coefficients (linear time)

def numTrees(self, n: int) -> int:
    C = 1
    for k in range(2,n+1):
        C = C*(n+k)/k
    return round(C)