# LeetCode 96: Unique Binary Search Trees

## Problem Restatement

We are given an integer `n`.

We need to count how many structurally unique binary search trees can be built using exactly the values:

```python
1, 2, 3, ..., n
```

Each value must be used exactly once.

The official problem asks for the number of structurally unique BSTs with exactly `n` nodes and unique values from `1` to `n`. The constraint is `1 <= n <= 19`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer `n` |
| Output | Number of structurally unique BSTs |
| Values used | Every value from `1` to `n` |
| Value reuse | Not allowed |
| Structure rule | Different shapes count as different BSTs |

Function shape:

```python
class Solution:
    def numTrees(self, n: int) -> int:
        ...
```

## Examples

Example 1:

```python
n = 3
```

There are five unique BSTs:

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

Answer:

```python
5
```

Example 2:

```python
n = 1
```

There is only one tree:

```python
1
```

Answer:

```python
1
```

## First Thought: Choose a Root

A BST has a strong ordering rule.

If we choose a root value `r`, then:

| Part | Values |
|---|---|
| Left subtree | Values smaller than `r` |
| Right subtree | Values greater than `r` |

For example, if:

```python
n = 5
root = 3
```

then the left subtree must use:

```python
[1, 2]
```

and the right subtree must use:

```python
[4, 5]
```

The root choice splits the problem into two smaller independent problems.

## Key Insight

For counting unique BSTs, the exact values matter less than how many values are available.

For example, the number of BSTs that can be built from:

```python
[1, 2, 3]
```

is the same as the number that can be built from:

```python
[4, 5, 6]
```

Both ranges contain three ordered values.

So define:

```python
dp[i]
```

as:

```python
the number of unique BSTs that can be built with i nodes
```

We want:

```python
dp[n]
```

## Base Cases

There is one BST with zero nodes:

```python
dp[0] = 1
```

This represents the empty subtree.

This is necessary because a root may have an empty left or right subtree.

There is also one BST with one node:

```python
dp[1] = 1
```

## Recurrence

Suppose we want to compute `dp[nodes]`.

Try each possible root position.

If the root has:

```python
left_count
```

nodes in the left subtree, then the right subtree has:

```python
right_count = nodes - 1 - left_count
```

The number of trees for this root shape is:

```python
dp[left_count] * dp[right_count]
```

because every left subtree can pair with every right subtree.

So:

```python
dp[nodes] = sum(dp[left_count] * dp[nodes - 1 - left_count])
```

for all:

```python
left_count = 0, 1, ..., nodes - 1
```

This is the Catalan recurrence.

## Algorithm

Create:

```python
dp = [0] * (n + 1)
```

Set:

```python
dp[0] = 1
dp[1] = 1
```

Then compute answers bottom-up.

For each `nodes` from `2` to `n`:

1. Try every possible number of nodes in the left subtree.
2. Compute the number of nodes in the right subtree.
3. Add `dp[left_count] * dp[right_count]` to `dp[nodes]`.

Return:

```python
dp[n]
```

## Walkthrough

Use:

```python
n = 3
```

Start:

```python
dp[0] = 1
dp[1] = 1
```

Compute `dp[2]`.

Possible splits:

| Left nodes | Right nodes | Count |
|---:|---:|---:|
| `0` | `1` | `dp[0] * dp[1] = 1` |
| `1` | `0` | `dp[1] * dp[0] = 1` |

So:

```python
dp[2] = 2
```

Compute `dp[3]`.

Possible splits:

| Left nodes | Right nodes | Count |
|---:|---:|---:|
| `0` | `2` | `dp[0] * dp[2] = 2` |
| `1` | `1` | `dp[1] * dp[1] = 1` |
| `2` | `0` | `dp[2] * dp[0] = 2` |

So:

```python
dp[3] = 2 + 1 + 2 = 5
```

Answer:

```python
5
```

## Correctness

The algorithm counts all valid BSTs by their root.

Every BST with `nodes` nodes has exactly one root. If its left subtree has `left_count` nodes, then its right subtree must have `nodes - 1 - left_count` nodes.

For that root split, any valid left subtree can be combined with any valid right subtree. These choices are independent because all left values are smaller than the root and all right values are larger than the root.

So the number of trees for one split is:

```python
dp[left_count] * dp[right_count]
```

The algorithm sums this over every possible `left_count`, which corresponds to every possible root position.

No tree is counted twice, because each tree has one root and therefore one left-subtree size.

No valid tree is missed, because every possible root position is included in the sum.

Therefore, `dp[n]` equals the number of structurally unique BSTs using values `1..n`.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n^2)` | For each node count, we try all left subtree sizes |
| Space | `O(n)` | The DP array stores results from `0` to `n` |

## Implementation

```python
class Solution:
    def numTrees(self, n: int) -> int:
        dp = [0] * (n + 1)

        dp[0] = 1
        dp[1] = 1

        for nodes in range(2, n + 1):
            for left_count in range(nodes):
                right_count = nodes - 1 - left_count
                dp[nodes] += dp[left_count] * dp[right_count]

        return dp[n]
```

## Code Explanation

Create a DP table:

```python
dp = [0] * (n + 1)
```

Set the base cases:

```python
dp[0] = 1
dp[1] = 1
```

Then fill the table from small node counts to large node counts:

```python
for nodes in range(2, n + 1):
```

For each total number of nodes, try every possible left subtree size:

```python
for left_count in range(nodes):
```

The remaining nodes go to the right subtree:

```python
right_count = nodes - 1 - left_count
```

Add all combinations:

```python
dp[nodes] += dp[left_count] * dp[right_count]
```

Finally, return the count for `n` nodes:

```python
return dp[n]
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.numTrees(1) == 1
    assert s.numTrees(2) == 2
    assert s.numTrees(3) == 5
    assert s.numTrees(4) == 14
    assert s.numTrees(5) == 42
    assert s.numTrees(19) == 1767263190

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `n = 1` | Smallest valid input |
| `n = 2` | One node can be root on either side |
| `n = 3` | Main example |
| `n = 4` | Checks next Catalan value |
| `n = 5` | Larger known value |
| `n = 19` | Maximum constraint |