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](https://i0.wp.com/totheinnovation.com/wp-content/uploads/2024/02/LeetCode-Problem-Solution.png?resize=200%2C200&ssl=1)
Unique Binary Search Trees LeetCode Solution
Table of Contents
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
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
}
};
Code language: PHP (php)
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];
}
}
Code language: PHP (php)
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];
};
Code language: JavaScript (javascript)
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]