Unique Binary Search Trees
MedPrompt
Given an integer n, return the number of structurally unique BST's (binary search trees) which has exactly n nodes of unique values from 1 to n.
Example 1:
Input: n = 3
Output: 5Example 2:
Input: n = 1
Output: 1
Constraints:
1 <= n <= 19
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly translates the recursive formula G(n) = sum_{i=1 to n} [G(i-1) * G(n-i)] into a recursive function. The function numTrees(n) will calculate the result by iterating from i = 1 to n, choosing i as the root, and recursively calling itself to find the number of unique BSTs for the left subtree (i-1 nodes) and the right subtree (n-i nodes). The sum of these products for all possible roots i gives the final answer.
Algorithm
- Define a function
numTrees(n). - Handle the base cases: if
nis 0 or 1, return 1. - Initialize a variable
totalto 0. - Iterate with a loop from
i = 1ton. In each iteration,irepresents the value of the root node. - For each
i, recursively callnumTrees(i - 1)to get the count of unique left subtrees andnumTrees(n - i)for the right subtrees. - Multiply the results from the recursive calls and add the product to
total. - After the loop, return
total.
Walkthrough
The core idea is to recognize that the number of unique BSTs with n nodes is the sum of possibilities for each node i (from 1 to n) being the root. If we choose i as the root, the i-1 nodes smaller than i will form the left subtree, and the n-i nodes larger than i will form the right subtree. The number of ways to form the left subtree is numTrees(i-1), and the number of ways to form the right subtree is numTrees(n-i). The total number of BSTs with i as the root is the product numTrees(i-1) * numTrees(n-i). We sum this product over all possible roots i from 1 to n. The base cases are numTrees(0) = 1 (one empty tree) and numTrees(1) = 1 (one tree with a single node).
public int numTrees(int n) { if (n <= 1) { return 1; } int count = 0; for (int i = 1; i <= n; i++) { // i is the root int leftTrees = numTrees(i - 1); int rightTrees = numTrees(n - i); count += leftTrees * rightTrees; } return count;}Complexity
Time
O(4^n / n^(3/2))
Space
O(n)
Trade-offs
Pros
Simple to understand and implement directly from the problem's recursive definition.
Cons
Extremely inefficient due to redundant calculations of the same subproblems.
Will likely result in a 'Time Limit Exceeded' error for
ngreater than around 15.
Solutions
Solution
public class Solution { public int NumTrees(int n) { int[] f = new int[n + 1]; f[0] = 1; for (int i = 1; i <= n; ++i) { for (int j = 0; j < i; ++j) { f[i] += f[j] * f[i - j - 1]; } } return f[n]; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.