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];
}


If You Like This Page Then Make Sure To Follow Us on Facebook, G News and Subscribe Our YouTube Channel. We will provide you updates daily.
Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment