Sponsored
Sponsored
The problem can be efficiently solved using Dynamic Programming. We notice that the number of unique BSTs can be determined as follows: for each node i from 1 to n, calculate the number of left and right subtrees which can form by considering i as the root. We can store these results in a table to avoid redundant work. The relationship can be expressed as:
G(n) = \sum_{i=1}^{n} (G(i-1) * G(n-i))where G(0) = 1 and G(1) = 1 are base cases.
Time Complexity: O(n^2)
Space Complexity: O(n)
1#include <stdio.h>
2
3int numTrees(int n) {
4 int dp[n + 1];
5 dp[0] = dp[1] = 1;
6 for (int i = 2; i <= n; i++) {
7 dp[i] = 0;
8 for (int j = 1; j <= i; j++) {
9 dp[i] += dp[j - 1] * dp[i - j];
10 }
11 }
12 return dp[n];
13}
14
15int main() {
16 int n = 3;
17 printf("%d\n", numTrees(n)); // Output: 5
18 return 0;
19}This C solution uses a dynamic programming array dp to store the number of unique BSTs for each number of nodes up to n. We initialize dp[0] and dp[1] to 1 as base cases. Then, for each number i, the number of unique BSTs can be calculated using previous results.
Using the Catalan number formula provides a mathematical way to solve the problem directly without iteration for up to moderate n. The nth catalan number C(n) is given by:
C(n) = \frac{1}{n+1}\binom{2n}{n}The C(n) represents the number of unique BSTs for n nodes. This can be computed efficiently using mathematical operations.
Time Complexity: O(n)
Space Complexity: O(1)
1using namespace std;
long long binomialCoeff(int n, int k) {
long long res = 1;
if (k > n - k)
k = n - k;
for (int i = 0; i < k; ++i) {
res *= (n - i);
res /= (i + 1);
}
return res;
}
int numTrees(int n) {
long long c = binomialCoeff(2 * n, n);
return (int)(c / (n + 1));
}
int main() {
int n = 3;
cout << numTrees(n) << endl; // Output: 5
return 0;
}This C++ solution calculates the Catalan number using the binomial coefficient by defining a helper function binomialCoeff. It computes the desired result in constant additional memory.