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)
1function numTrees(n) {
2 const dp = new Array(n + 1).fill(0);
3 dp[0] = dp[1] = 1;
4 for (let i = 2; i <= n; i++) {
5 for (let j = 1; j <= i; j++) {
6 dp[i] += dp[j - 1] * dp[i - j];
7 }
8 }
9 return dp[n];
10}
11
12const n = 3;
13console.log(numTrees(n)); // Output: 5This 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
public class UniqueBSTCatalan {
public long BinomialCoeff(int n, int k) {
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;
}
public int NumTrees(int n) {
long c = BinomialCoeff(2 * n, n);
return (int)(c / (n + 1));
}
public static void Main(string[] args) {
UniqueBSTCatalan solution = new UniqueBSTCatalan();
int n = 3;
Console.WriteLine(solution.NumTrees(n)); // Output: 5
}
}C# solution that computes the number of unique BSTs using a mathematical approach with the binomial coefficient function. The result gives the nth Catalan number formed from integer arithmetic.