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)
1
This C solution uses the Catalan number formula leveraging combination calculations. The function binomialCoeff computes C(2n, n) before dividing by n+1 to get the nth Catalan number.