# 96. Unique Binary Search Trees I

Reference: LeetCode EPI 15.9
Difficulty: Medium

## Problem

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

Example:

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

Here is the recurrence tree:

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

Therefore, we can use a hash map or an integer array to store calculated $G(n)$. Here is the hash map version.

Here is the recurrence tree:

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)$

Note: Notice that it is G[i - j] instead of G[n - j] and it is j <= i instead of j <= 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.

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.

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

Comment
Junhao Wang
a software engineering cat