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)
1class UniqueBST:
2 def numTrees(self, n: int) -> int:
3 dp = [0] * (n + 1)
4 dp[0], dp[1] = 1, 1
5 for i in range(2, n + 1):
6 for j in range(1, i + 1):
7 dp[i] += dp[j - 1] * dp[i - j]
8 return dp[n]
9
10if __name__ == "__main__":
11 solution = UniqueBST()
12 print(solution.numTrees(3)) # Output: 5This Python solution utilizes a dynamic programming list to cache the results of subproblems. Starting from initialized base cases, it fills up to n by considering various possibilities of splitting nodes into 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
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.