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)
1using System;
2
3public class UniqueBST {
4 public int NumTrees(int n) {
5 int[] dp = new int[n + 1];
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
15 public static void Main(string[] args) {
16 UniqueBST solution = new UniqueBST();
17 int n = 3;
18 Console.WriteLine(solution.NumTrees(n)); // Output: 5
19 }
20}The C# solution leverages a dynamic programming array to store results for subproblems similar to other language implementations. Each element is computed by considering each valid splitting point for left and right subtrees.
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.