Unique Binary Search Trees

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

Read more about Catalan_number on Wikipedia (opens new window) and this great Chinese post (opens new window).

# Solution

CnC_n means the nth Catalna number.

The first Catalan numbers for n=0,1,2,n = 0, 1, 2, \cdots are: 1,1,2,5,14,42,1321, 1, 2, 5, 14, 42, 132 ...

The number of structurally unique BST's that store values 1n1 \cdots n is CnC_n.

# Catalan Number

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

# Recursive Formula 1

Cn=i=1nCi1CniC_{n}=\sum_{i=1}^n C_{i-1} C_{n-i}

Complexity

time: O(n2)O(n^2)
space: O(n)O(n)

def numTrees(self, n: int) -> int:
    C = [0 for _ in range(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

Cn=2(2n1)n+1Cn1C_{n}=\frac{2(2n-1)}{n+1} C_{n-1}

Complexity

time: O(n)O(n)
space: O(1)O(1)

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

Cn=1n+1(2nn)=(2n)!(n+1)!n!=k=2nn+kkC_{n}=\frac{1}{n+1} \binom{2n}{n}=\frac{(2n)!}{(n+1)! n!}=\prod_{k=2}^{n} \frac{n+k}{k}

Complexity

time: O(n)O(n)
space: O(1)O(1)

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