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: Given an integer n, count how many structurally unique binary search trees can be built using values from 1 to n. Each number must appear exactly once. Different tree shapes count as different BSTs even if they contain the same values.
Approach 1: Dynamic Programming (Time: O(n2), Space: O(n))
The key observation comes from the BST property: when you pick a value i as the root, all numbers 1..i-1 must form the left subtree and i+1..n must form the right subtree. The number of unique BSTs with i as root equals the number of possible left subtrees multiplied by the number of right subtrees. Define dp[k] as the number of BSTs that can be formed using k nodes. For each total node count k, iterate every node as root and accumulate dp[left] * dp[right]. This bottom-up dynamic programming approach builds answers from smaller subtree sizes.
Initialize dp[0] = 1 and dp[1] = 1 because an empty tree and a single-node tree both have exactly one valid structure. For each nodes from 2 to n, iterate possible roots and compute subtree combinations. The nested iteration leads to O(n2) time complexity. Space stays O(n) for the DP array.
Approach 2: Catalan Number Formula (Time: O(n), Space: O(1))
This problem is a direct application of the Catalan sequence, a classic result from math and combinatorics. The number of unique BSTs with n nodes equals the nth Catalan number. The closed-form formula is C(n) = (1 / (n + 1)) * binomial(2n, n). Instead of computing large factorials, you can iteratively calculate the binomial coefficient using multiplication and division to avoid overflow.
The Catalan interpretation works because every BST can be uniquely defined by choosing a root and recursively combining valid left and right subtree counts. This is exactly the recurrence used in the DP solution, but the mathematical formula collapses the recurrence into a direct computation. The iterative Catalan computation runs in O(n) time with constant extra space.
Recommended for interviews: Start with the Dynamic Programming approach. It demonstrates understanding of the BST root-partition idea and shows you can translate a recursive counting problem into a DP recurrence. Interviewers usually expect dp[n] = sum(dp[left] * dp[right]). Mentioning the Catalan number formula afterward signals deeper algorithm knowledge and familiarity with common combinatorial patterns.
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
C++
Java
Python
C#
JavaScript
Go
TypeScript
Rust
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.
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^2) | O(n) | Best interview explanation; shows BST root partition and DP recurrence clearly |
| Catalan Number Formula | O(n) | O(1) | When you recognize the Catalan pattern and want a mathematically optimized solution |
Unique Binary Search Trees - Leetcode 96 - Python Dynamic Programming • NeetCode • 91,131 views views
Watch 9 more video solutions →Practice Unique Binary Search Trees with our built-in code editor and test cases.
Practice on FleetCode