In this guide, you will get 96. Unique Binary Search Trees LeetCode Solution with the best time and space complexity. The solution to Unique Binary Search Trees problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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
Complexity Analysis
Time Complexity: O(n^2)
Space Complexity: O(n)
96. Unique Binary Search Trees LeetCode Solution in C++
class Solution {
public:
int numTrees(int n) {
// dp[i] := the number of unique BST's that store values 1..i
vector<int> dp(n + 1);
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];
}
}; /* code provided by PROGIEZ */
96. Unique Binary Search Trees LeetCode Solution in Java
class Solution {
public int numTrees(int n) {
// dp[i] := the number of unique BST's that store values 1..i
int[] dp = new int[n + 1];
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];
}
} // code provided by PROGIEZ
96. Unique Binary Search Trees LeetCode Solution in Python
class Solution:
def numTrees(self, n: int) -> int:
# dp[i] := the number of unique BST's that store values 1..i
dp = [1, 1] + [0] * (n - 1)
for i in range(2, n + 1):
for j in range(i):
dp[i] += dp[j] * dp[i - j - 1]
return dp[n] # code by PROGIEZ
