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 <= 19Problem Overview: You need to count how many structurally unique binary search trees (BSTs) can be built using values 1..n. Every tree must follow the BST rule: left subtree values are smaller than the root and right subtree values are larger.
Approach 1: Dynamic Programming (O(n²) time, O(n) space)
The key observation: if you choose a number i as the root, all numbers 1..i-1 form the left subtree and i+1..n form the right subtree. The number of BSTs with root i equals the number of left subtree combinations multiplied by the number of right subtree combinations. Define dp[k] as the number of unique BSTs that can be built with k nodes. For each nodes from 1..n, iterate every possible root and accumulate dp[left] * dp[right]. This bottom-up dynamic programming approach avoids recomputing subtree counts and directly models the recursive structure of binary search trees. Time complexity is O(n²) due to the nested loops over nodes and root choices, while space complexity is O(n) for the DP array.
Approach 2: Catalan Number Formula (O(n) time, O(1) space)
The result of this problem follows the Catalan sequence, a well-known pattern in combinatorics. The number of unique BSTs with n nodes equals the nth Catalan number: C(n) = (2n)! / ((n + 1)! * n!). Instead of computing factorials directly, you can iteratively compute the value using the recurrence C(n+1) = C(n) * 2(2n+1)/(n+2). This avoids large factorial calculations and keeps the computation efficient. The approach comes from counting valid tree structures formed under combinatorial math constraints and works because each BST structure corresponds to a Catalan arrangement. Time complexity is O(n) with O(1) extra space.
Recommended for interviews: The dynamic programming solution is what most interviewers expect first. It demonstrates that you understand how BST structure splits into independent subproblems and how to model that with dynamic programming. After presenting the DP approach, mentioning that the result corresponds to the Catalan sequence shows deeper algorithmic knowledge. DP proves you can derive the recurrence from the problem itself, while the Catalan formula shows familiarity with classic counting patterns in tree problems.
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.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2)
Space Complexity: O(n)
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.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n)
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Dynamic Programming | Time Complexity: O(n^2) |
| Catalan Number Formula | Time Complexity: O(n) |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming | O(n²) | O(n) | Best for interviews; clearly derives the recurrence by considering every root and combining left/right subtree counts. |
| Catalan Number Formula | O(n) | O(1) | When you recognize the Catalan pattern or want the most optimized mathematical solution. |
Unique Binary Search Trees - Leetcode 96 - Python Dynamic Programming • NeetCode • 77,933 views views
Watch 9 more video solutions →Practice Unique Binary Search Trees with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor