96. Unique Binary Search Trees

Given an integer n, return the number of structurally unique BST's (binary search trees) which has exactly n nodes of unique values from 1 to n.

Example 1:

Input: n = 3
Output: 5

Example 2:

Input: n = 1
Output: 1

Constraints:

• 1 <= n <= 19

Approach 1:

Dynamic Programming

As we can see ,

• number of unique BST for a tree with n=1 is 1
• number of unique BST for a tree with n=2 is 2
• number of unique BST for a tree with n=3 is

This is nothing but Catalan’s number

Cn=C0*Cn-1 +C1*Cn-2….. +Cn-1*C0

The code is given below

class Solution(object):
    def numTrees(self, n):
        dp=[0 for i in range(n+2)]
        dp[0]=1
        dp[1]=1
        dp[2]=2
        for i in range(2,n+1):
            sum_=0
            for j in range(0,i):
                m,k=j,i-1-j    
                sum_+=dp[m]*dp[k]
            dp[i]=sum_
        return dp[n]

Time : O(n²)

Space: O(n)

Approach 2:

Using formula

Simplifying the Catalans number we get

Cn = 2nCn/n+1

class Solution(object):
    def numTrees(self, n):
        return(math.factorial(2*n)/(math.factorial(n)*math.factorial(n+1)))

Assuming the factorial function takes of order of n time.

Time :O(n)

Space :O(1)