Last updated on October 9th, 2024 at 10:45 pm

Here, We see Unique Binary Search Trees LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Unique Binary Search Trees LeetCode Solution

Problem Statement

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

1. Unique Binary Search Trees Leetcode Solution C++

class Solution {
public:
    int numTrees(int n) {
        vector<int>result(n+1,0); //Initializing vector with 0
        result[1]=result[0]=1;
        for(int i=2;i<=n;i++)
        {
            for(int j=0;j<i;j++)
            {
                result[i]+=result[j]*result[i-j-1]; //Calculating C(i) to use for C(i+1) and storing it in result
            }
        }
        return result[n]; //return answer        
    }
};

2. Unique Binary Search Trees Leetcode Solution Java

class Solution {
    public int numTrees(int n) {
    int [] G = new int[n+1];
    G[0] = G[1] = 1;
    
   for(int i=2; i<=n; ++i) {
     for(int j=1; j<=i; ++j) {
       G[i] += G[j-1] * G[i-j];
     }
   }
   return G[n];    
     }
 }

3. Unique Binary Search Trees Leetcode Solution JavaScript

var numTrees = function(n) {
    let G = new Array(n+1).fill(0);
    G[0] = 1;
    G[1] = 1;
    for (let i=2;i<=n;i++) {
        for (let j=1;j<=i;j++) {
            G[i]+=G[j-1] * G[i - j];
        }
    }
    return G[n];    
};

4. Unique Binary Search Trees Leetcode Solution Python

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