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 <= 19
Unique Binary Search Trees Solutions
✅Time: O(n)
✅Space: O(n)
C++
class Solution {
public:
int numTrees(int n) {
// G[i] := # of unique BST's that store values 1..i
vector<int> G(n + 1);
G[0] = 1;
G[1] = 1;
for (int i = 2; i <= n; ++i)
for (int j = 0; j < i; ++j)
G[i] += G[j] * G[i - j - 1];
return G[n];
}
};
Java
class Solution {
public int numTrees(int n) {
// G[i] := # of unique BST's that store values 1..i
int[] G = new int[n + 1];
G[0] = 1;
G[1] = 1;
for (int i = 2; i <= n; ++i)
for (int j = 0; j < i; ++j)
G[i] += G[j] * G[i - j - 1];
return G[n];
}
}
Python
class Solution:
def numTrees(self, n: int) -> int:
# G[i] := # of unique BST's that store values 1..i
G = [1, 1] + [0] * (n - 1)
for i in range(2, n + 1):
for j in range(i):
G[i] += G[j] * G[i - j - 1]
return G[n]
Watch Tutorial
Checkout more Solutions here