Problem
Given n, how many structurally unique BST's (binary search trees) that store values 1...n?
For example,
Given n = 3, there are a total of 5 unique BST's.
Clarification
First of all, we are are counting NONISOMORPHIC binary trees. What that means?
Nonformal definition of binary tree isomorphism:
Two binary trees are isomorphic, if you can erase a number in each node and two resulting trees will have the same shape.
Example
Two binary trees T1 and T2 below are isomorphic, since we can erase all the values and two resulting binary trees will have the same shape(T').
Corollary
Okey, finally we understand that since we are counting nonisomorphic binary trees we do not care about values in the nodes, we only know that there are n nodes in the tree.
Intuition
Let's denote B_n  binary tree with exactly n nodes.
Okay, first notice that our binary trees may differ in the size of the left and right subtree.
How many nodes can be present in left subtree?
We have one node as a root, so the number of the nodes in the left subtree is in range [0, n  1]. From that we can derive the number of the nodes in the right subtree: if we have i nodes in the left subtree and one node as a root, then we have n  i  1 nodes in the right subtree.
We have to count all possible sizes of the left subtree. The size of the right subtree determines uniquely from the size of the left subtree.
Also, for each left subtree with i nodes we can pick any from B_{n  i  1} right subtrees, since they are completely independent.
Finally, we derive a formula:
B_n = Σ B_{i} * B_{n  i  1}, i from 0 to n  1.
I have to say that B_n is called the nth Catalan number. More information can be found here: https://en.wikipedia.org/wiki/Catalan_number
Approach #1 Simple Recursion [Time Limit Exceeded]
Intuition
Just compute the Catalan numbers using the formula B_n = Σ B_{i} * B_{n  i  1} recursively.
Base case: B_0 = 1 and B_1 = 1.
Java
class Solution {
public int catalan(int n) {
if (n == 1  n == 0) { //base case
return 1;
}
int ans = 0;
for (int i = 0; i < n; i++) { //sum over all i
ans += catalan(i) * catalan(n  i  1);
}
return ans;
}
public int numTrees(int n) {
return catalan(n);
}
}
Complexity Analysis
 Time complexity : O(4^n).
It can be proven that Catalan numbers grow exponentially.
Formal proof can be found here:
https://math.stackexchange.com/questions/1986247/asymptoticapproximationofcatalannumbers
 Space complexity : O(1). No auxiliary data structures.
Approach #2 Dynamic Programing [Accepted]
Intuition
Basically we use the same approach as above, but we apply memoization.
Here dp[i]  number of structurally unique BST's with n nodes.
We calculate dp[i] for i from 1 to n. In the inner loop we iterate over the size of the left subtree.
Java
class Solution {
public int numTrees(int n) {
int[] dp = new int[n + 1];
dp[0] = 1; //base case
for (int i = 1; i < n + 1; i++) { //evaluate all dp[i]
for (int left = 0; left < i; left++) {
//loop over size of the left subtree
dp[i] += dp[left] * dp[i  left  1];
}
}
return dp[n];
}
}
Complexity Analysis

Time complexity : O(n^2). We have to evaluate the following sum: 1 + 2 + 3 + ... + n, but this is a geometric series so: 1 + 2 + 3 + ... + n = n * (n + 1) / 2.

Space complexity : O(n). Have to store an array.
Approach #3 Using formula [Accepted]
Intuition
We can also use this fromula for Catalan numbers:
B_n = (n + 2} * (n + 3) * (n + 4) * (n + n) / (2 * 3 * 4 * ... * n)
Java
class Solution {
public int numTrees(int n) {
double ans = 1;
for (int i = 2; i < n + 1; i++) {
ans *= (n + i);
ans /= i;
}
//already for n = 19
//it gives an error due to precision loss
if (n == 19) {
return (int) ans + 1;
}
return (int) ans;
}
}
Complexity Analysis

Time complexity : O(n). We iterate from 2 to n + 1.

Space complexity : O(1). No auxiliary data structures.