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 <vector>
2using namespace std;
3
4int numTrees(int n) {
5 vector<int> dp(n + 1, 0);
6 dp[0] = dp[1] = 1;
7 for (int i = 2; i <= n; ++i) {
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 int result = numTrees(n);
18 // Output: 5
19 return 0;
20}This C++ solution uses a dynamic programming vector to store results. By iterating from 2 to n, for each number i, we accumulate the number of possible trees by considering each number j as a root.
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.