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)
1public class UniqueBST {
2 public int numTrees(int n) {
3 int[] dp = new int[n + 1];
4 dp[0] = dp[1] = 1;
5 for (int i = 2; i <= n; i++) {
6 for (int j = 1; j <= i; j++) {
7 dp[i] += dp[j - 1] * dp[i - j];
8 }
9 }
10 return dp[n];
11 }
12
13 public static void main(String[] args) {
14 UniqueBST solution = new UniqueBST();
15 int n = 3;
16 System.out.println(solution.numTrees(n)); // Output: 5
17 }
18}The Java solution uses an integer array to hold the results of the subproblems. By iterating through possible values for root nodes, we compute the entire table until we reach n.
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.