> For the complete documentation index, see [llms.txt](https://keerthisreeraghu.gitbook.io/june-leetcoding-challenge/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://keerthisreeraghu.gitbook.io/june-leetcoding-challenge/week-4/unique-binary-search-trees.md).

# Unique Binary Search Trees

LeetCode Problem #96 (Medium)

## Problem Statement

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

## Testcase

```
Example 1:

Input: 3
Output: 5
Explanation:
Given n = 3, there are a total of 5 unique BST's:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3
```

## Prerequisite Knowledge

### Dynamic Programming

Refer to the *Prerequisite Knowledge* section in **Coin Change 2**:

{% content-ref url="/pages/-M9K9cisnWuSztRUJF2y" %}
[Coin Change 2](/june-leetcoding-challenge/week-1/coin-change-2.md)
{% endcontent-ref %}

### Catalan Number

A sequence of non-negative numbers which commonly appears in combinatorial problems is known as Catalan Numbers. It often involves recursively defined objects.

**Euler's Polygon Division Problem** asks the question, *"In how many ways can a regular `n-gon` be divided into `n-2` triangles if different orientations are counted separately?"*

In tree enumeration problems such as the one given above, the solution involves the Catalan Sequence.

![Source: https://mathworld.wolfram.com/CatalanNumber.html](https://3540593164-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M9DtKfC4RdOdz3G4SbS%2F-MAdWhl7oW6jMfrR0OG6%2F-MAdi6neGzX6TgvZLnAV%2Fimage.png?alt=media\&token=221bb002-9533-4727-9014-3379ca7eceff)

#### Formula

The nth Catalan Number is given by:

```
C(n) = (2n)! / ((n + 1)! * n!)
```

#### Catalan Series

The first few Catalan Numbers starting from 0 are:`1, 1, 2, 5, 14, 42, 132, 429, 1430,...`

## Problem Explanation

In this problem, we must find the number of unique binary search trees that can be formed using a given number of nodes. In order to calculate the number of arrangements of nodes, we must choose the number of nodes in the left sub-tree and the number of nodes in the right sub-tree while considering each node as the root node.

#### Example

Consider `n = 5`. We can derive the following combinations:

1. `root = 1`->`left nodes = 0` | `right nodes = 4`->`f[0]*f[4]`
2. `root = 2`->`left nodes = 1` | `right nodes = 3`->`f[1]*f[3]`
3. `root = 3`->`left nodes = 2` | `right nodes = 2`->`f[2]*f[2]`
4. `root = 4`->`left nodes = 3` | `right nodes = 1`->`f[3]*f[1]`
5. `root = 5`->`left nodes = 4` | `right nodes = 0`->`f[4]*f[0]`

Therefore, for `n = 5` nodes, the total number of binary search trees can be represented as:\
`f[5] = f[0]*f[4] + f[1]*f[3] + f[2]*f[2] + f[3]*f[1] + f[4]*f[0]`

#### Generalized Formula

`f[n] = f[0]*f[n-1] + f[1]*f[n-2] + ... + f[n-2]*f[1] + f[n-1]*f[0]`

## Algorithm

### Bottom-Up DP Approach

The intuitive approach would be to use a bottom-up dynamic programming approach to construct unique binary search trees by using each node of the tree as a root node to derive different combinations. 

The recursive formula to find the total number of combinations is:

```
G(n) = G(0) * G(n-1) + G(1) * G(n-2) + … + G(n-1) * G(0)
```

1. Create a vector to store the solutions of each sub-problem.
2. Initialize `dp[0]` as 1 to account for the first solution with the root being set as 1.
3. For each node in the tree, compute the number of unique binary search trees that can be formed using this node as the root node, by applying the formula: `dp[i] += dp[j-1] * dp[i-j]`.

{% hint style="info" %}
Time Complexity: O(m\*n)
{% endhint %}

### Mathematical Approach

In this approach, we use the Nth Catalan Number formula to find the number of ways in which the nodes can be arranged to form unique binary search trees.

```
C(n) = (2n)! / ((n + 1)! * n!)
```

The reason for this can be attributed to the pattern that can be observed when we examine the number of nodes and the number of possible combinations that could be formed.

1. `n = 1`->`c = 1`
2. `n = 2`->`c = 2`
3. `n = 3`->`c = 5`
4. `n = 4`->`c = 14`
5. `n = 5`->`c = 42`

From the values of `c` that we have obtained, we can observe that the pattern is similar to that of the Catalan Numbers series as illustrated in the *Prerequisite Knowledge* section. 

{% hint style="info" %}
Time Complexity: O(n)
{% endhint %}

## Code

{% code title="Dynamic Programming Approach" %}

```cpp
int numTrees(int n) {
    vector<int> dp(n + 1, 0);
    // When 1 is set as root, 
    // left subtree = 0 children, right subtree = dp[n - 1] children
    // Set dp[0] = 1
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            // If k is set as the root node,
            // left subtree = (k - 1) children
            // right subtree = (n - k) children
            dp[i] += dp[j - 1] * dp[i - j];
        }
    }
    return dp[n];
}
```

{% endcode %}

{% code title="Mathematical Approach" %}

```cpp
int numTrees(int n) {
    long long count = 1;
    for(int i = n + 1; i <= 2 * n; i++) {
        count = count * i / (i - n);
    }
    return count / (n + 1);
}
```

{% endcode %}