Reference: LeetCode EPI 15.9

Difficulty: Medium

My Post: Summary of All Solutions in Java with Explanations

## Problem

Given $n$, how many structurally unique BST’s (binary search trees) that store values

`1 ... n`

?

**Example:**

1 | Input: 3 |

## Analysis

### DP (Recursion)

Reference: LeetCode Solution

Given a sequence $1, 2, \ldots, n$, we enumerate each number `i`

in the sequence and take it as the root to form binary trees.

We define two functions:

- $G(n)$: the number of unique BST for a sequence of length
`n`

(number of nodes). - $F(i, n)$: the number of unique BST, where the number
`i`

(`1 <= i <= n`

) is the root.

We construct $G(n)$ by the sum of $F(i, n)$:

$$G(n) = \sum^n_{i=1}F(i, n) = F(1, n) + F(2, n) + \ldots + F(n, n)$$

Notice that when we select `i`

as a root i.e. $F(i, n)$, we have `i - 1`

nodes which can be used to form a left subtree; similarly we have `n - i`

nodes to form a right subtree.

$$F(i,n) = G(i - 1) \times G(n - i)$$

Thus, $F(i, n)$ can be calculated by the product of the number of unique BST with `i - 1`

nodes and the number of unique BST with `n - i`

nodes. **Uniqueness is guaranteed by the sizes of the left subtree and the right subtree.**

Particularly, consider two base cases when `i = 1`

and `i = 2`

:

`i = 1`

: $F(1, n) = G(0) \times G(n - 1)$. The empty left subtree is still a subtree, so $G(0) = 1$.`i = 2`

: $F(2, n) = G(1) \times G(n - 2)$. With one node we can only construct one unique left subtree, so $G(1) = 1$.

Finally, we have the recurrence:

$$G(n) = \sum^n_{i=1}F(i,n) = \sum^n_{i=1} G(i - 1) \times G(n - i)$$

$$\text{where}\ \ G(0)=1, G(1)=1$$

Here is the code without memoization.

1 | // numTress(n) is G(n) |

Here is the recurrence tree:

1 | G(4) |

$C(N) = N \times N!$

**Time:** It is at most bounded by $O(N \times N!)$. A tighter bound would be Catalan number times $N$ since we’ve done $N$ times, which is $N \times G_N = O(N\times\frac{4^N}{N^{3/2}}) = O(\frac{4^N}{N^{1/2}})$.**Space:** $O(N)$

Examining the recurrence carefully, we find that there are repeated calculations.

1 | G(3) = G(0) x G(2) // i = 1 |

Therefore, we can use a `hash map`

or an `integer array`

to store calculated $G(n)$. Here is the hash map version.

1 | Map<Integer, Integer> map = new HashMap<>(); |

Here is the recurrence tree:

1 | G(4) |

**Note:** Without memoization, the time complexity is upper bounded by $O(N \times N!)$.

By calculating the leftmost nodes, we have $G(0), G(1), \ldots, G(N)$, which takes $O(N)$ time. Besides, we have to do product computations at each level, which takes $2 + 3 + 4 + \ldots + N = O(N^2)$ time in total.

**Time:** $O(N^2)$**Space:** $O(N)$ because of call stacks.

### DP (Iteration)

By observation, we can construct our solution by a bottom-up approach.

The recurrence formula: $G(n) = \sum^n_i G(i - 1) \times G(n - i)$

For example, $G(4) = G(0) \times G(3) + G(1) \times G(2) + G(2) \times G(1) + G(3) \times G(0)$

1 | G(0) G(1) |

**Note:** Notice that it is `G[i - j]`

instead of `G[n - j]`

and it is `j <= i`

instead of `j <= n`

.

1 | public int numTrees(int n) { |

**Time:** $O(N^2)$**Space:** $O(N)$

### Mathematical Deduction

The sequence of $G(n)$ function results is known as `Catelan number`

$C_n$.

$$C_0 = 1,\ \ \ C_{n+1} = \frac{2(2n+1)}{n+2}C_n$$

**Note:** Use `long`

type.

1 | C = 2 * (2 * i + 1) / (i + 2) * C; |

If we put `C`

at the end of the statement, the result is not correct. **Do all multiplications first!** For example, when `i = 2`

and `C_2 = 2`

, we would have:

`C = 2 * (2 * 2 + 1) / (2 + 2) * C_2 = 2 * (5) / 4 * 2 = 10 / 4 * 2 = 4`

- instead of
`C = 2 * 10 / 4 = 5`

.

1 | public int numTrees(int n) { |

**Time:** $O(N)$**Space:** $O(1)$