Unique Binary Search Tree Problem Solution

Unique Binary Search Tree Problem: 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.

Input: n = 3
Output: 5

Unique Binary Search Tree Problem Solution

Problem Solution In Python

class Solution(object):
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n==0 or n==1:
            return 1
        
        dp = [0]*(n+1)
        dp[0] = 1
        dp[1] = 1
        
        
        for i in range(2, n+1):
            for j in range(i):
                dp[i]+=dp[i-j-1] * dp[j]
                
        return dp[n]

Problem Solution In Java

public class Solution {
    public int numTrees(int n) {
        int[] record = new int[n+1];
        record[0] = 1;
        record[1] = 1;
        return numTrees(n, record);
    }
    
    public int numTrees(int n, int[] record) {
        int result = 0;
        for(int i=1; i<=n; i++) {
            int tmp = 1;
            int left = i - 1;
            int right = n - i;
            if(record[left] > 0) {
                tmp *= record[left];
            } else {
                tmp *= numTrees(left, record);
            }
            if(record[right] > 0) {
                tmp *= record[right];
            } else {
                tmp *= numTrees(right, record);
            }
            result += tmp;
        }
        record[n] = result;
        return result;
    }
}

Problem Solution In C++

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n+1, 0);
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; ++i) {
            for (int j = 0; j < i; j++) {
                dp[i] += dp[j] * dp[i-j-1];
            }
        }
        return dp[n];
    }
};

Problem Solution In C

int solutions[1024]={1,1,};
int calculated = 1;
int numTrees(int n) {
    if(n<calculated)
        return solutions[n];
    int start = calculated+1;
    for(int loop = start;loop<n+1;loop++){
        int sum = 0;
        for(int i=0;i<loop;i++){
            sum += solutions[i]*solutions[loop-i-1];
        }
        solutions[loop]=sum;
    }
    calculated = n;
    return solutions[n];
}