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)
This JavaScript solution iteratively calculates the number of unique BSTs using a dynamic programming approach, where dp[i] depends on the product of possible left and right subtrees for potential root nodes.
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)
1#include <iostream>
2using namespace std;
3
4long long binomialCoeff(int n, int k) {
5 long long res = 1;
6 if (k > n - k)
7 k = n - k;
8 for (int i = 0; i < k; ++i) {
9 res *= (n - i);
10 res /= (i + 1);
11 }
12 return res;
13}
14
15int numTrees(int n) {
16 long long c = binomialCoeff(2 * n, n);
17 return (int)(c / (n + 1));
18}
19
20int main() {
21 int n = 3;
22 cout << numTrees(n) << endl; // Output: 5
23 return 0;
24}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.