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)
This 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)
1import math
2
3class UniqueBSTCatalan:
4 def numTrees(self, n: int) -> int:
5 return math.comb(2 * n, n) // (n + 1)
6
7if __name__ == "__main__":
8 solution = UniqueBSTCatalan()
9 print(solution.numTrees(3)) # Output: 5Python simplification using the built-in math.comb function efficiently computes the Catalan number directly from binomial coefficient calculations. This provides a concise way to achieve the solution.