# Solution by I_am_Hokage

• #### 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 NON-ISOMORPHIC binary trees. What that means?

Non-formal 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 non-isomorphic 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 n-th 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/asymptotic-approximation-of-catalan-numbers

• 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;
}

//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.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.