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: 5
Example 2:
Input: n = 1 Output: 1
Constraints:
1 <= n <= 19The key insight in #96 Unique Binary Search Trees is that we are not generating trees but counting how many structurally unique BSTs can be formed using values from 1..n. Because a Binary Search Tree depends on the choice of root, each value can be considered as the root, splitting the remaining numbers into a left subtree and a right subtree.
If we choose a number i as the root, then all numbers less than i must form the left subtree and all numbers greater than i must form the right subtree. The total number of trees for that root becomes the product of possibilities from the left and right sides. Summing this for all possible roots leads to a classic dynamic programming recurrence.
This pattern forms the well‑known Catalan number sequence. Using DP, we build results from smaller subtree sizes up to n. The approach runs in O(n²) time due to the nested root choices and uses O(n) space for the DP array.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming (Catalan Recurrence) | O(n^2) | O(n) |
| Mathematical Catalan Formula | O(n) | O(1) |
NeetCode
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 <stdio.h>
2
3int numTrees(int n) {
4 int dp[n + 1];
5 dp[0]
This C solution uses a dynamic programming array dp to store the number of unique BSTs for each number of nodes up to n. We initialize dp[0] and dp[1] to 1 as base cases. Then, for each number i, the number of unique BSTs can be calculated using previous results.
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
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem or its variations frequently appear in FAANG-style interviews. Interviewers use it to test understanding of dynamic programming, recursion patterns, and tree-related combinatorics.
The optimal approach uses dynamic programming based on the Catalan number recurrence. For each possible root, the number of unique BSTs equals the product of possible left and right subtree combinations. Summing these for all roots from 1 to n gives the final count.
The recurrence formed by splitting nodes into left and right subtrees matches the Catalan number formula. Each root divides the remaining nodes into two independent subproblems whose combinations multiply together. This structure naturally produces the Catalan sequence.
Dynamic programming is the most important concept because the problem builds solutions for larger n from previously computed subtree counts. Understanding BST properties and combinatorics also helps recognize the Catalan pattern.
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.