Unique Binary Search Trees — Solution in Python, Java & C++
Unique Binary Search Trees solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Unique Binary Search Trees is a medium coding problem on dynamic programming and math, asked in Amazon, Google and Adobe interviews.
- Difficulty: Medium
- Topics: Dynamic Programming, Math
- Asked at: Amazon, Google, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an integer n, return the number of structurally distinct binary search trees that hold exactly the values 1 through n.
Example 1
Input: n = 3
Output: 5
Example 2
Input: n = 1
Output: 1
Example 3
Input: n = 5
Output: 42
Constraints
1 <= n <= 19The answer fits in a 32-bit integer.
Hints for Unique Binary Search Trees
Hint 1
Fix which value sits at the root — say
k.Hint 2
Everything below
kforms the left subtree and everything above forms the right, independently.Hint 3
So
G(n) = Σ G(k-1) · G(n-k)forkfrom 1 ton, withG(0) = 1.
How to solve Unique Binary Search Trees
Choosing the root splits the value range into two independent sub-ranges. The count depends only on the sizes of those ranges, not on the actual values — which gives the Catalan recurrence.
Approach
- Set
G[0] = 1(the empty tree counts as one shape). - For each
ifrom 1 ton, sumG[root-1] * G[i-root]over every possible root position. - Return
G[n].
Why it works
A BST on {1..n} with root k has a left subtree over {1..k-1} and a right subtree over {k+1..n}. The shapes available depend only on how many values each side holds, so the counts multiply and the roots partition the possibilities.
Complexity
- Time —
O(n²) - Space —
O(n)
Pitfalls
G[0] = 0collapses everything to zero — an empty subtree is one valid shape.- At
n = 19the answer is 1,767,263,190, just inside a signed 32-bit integer; largernwould overflow. - The direct Catalan formula works too but needs care with integer division.
Reference solution
Python
def numTrees(n: int) -> int:
g = [0] * (n + 1)
g[0] = 1
for i in range(1, n + 1):
for root in range(1, i + 1):
g[i] += g[root - 1] * g[i - root]
return g[n]Java
public static int numTrees(int n) {
long[] g = new long[n + 1];
g[0] = 1;
for (int i = 1; i <= n; i++) {
for (int root = 1; root <= i; root++) {
g[i] += g[root - 1] * g[i - root];
}
}
return (int) g[n];
}C++
int numTrees(int n) {
vector<long long> g(n + 1, 0);
g[0] = 1;
for (int i = 1; i <= n; i++) {
for (int root = 1; root <= i; root++) {
g[i] += g[root - 1] * g[i - root];
}
}
return (int) g[n];
}JavaScript
var numTrees = function(n) {
const g = new Array(n + 1).fill(0);
g[0] = 1;
for (let i = 1; i <= n; i++) {
for (let root = 1; root <= i; root++) {
g[i] += g[root - 1] * g[i - root];
}
}
return g[n];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 402 dynamic programming problems · the whole catalogue
Learn the technique: Dynamic Programming