# LeetCode 95: Unique Binary Search Trees II

## Problem Restatement

We are given an integer `n`.

We need to generate all structurally unique binary search trees that contain exactly the values:

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

Each value must be used exactly once.

The answer may be returned in any order.

A binary search tree has this rule:

| Node relation | Required value rule |
|---|---|
| Left subtree | Values smaller than the root |
| Right subtree | Values greater than the root |

The official constraints are `1 <= n <= 8`. The problem asks for all structurally unique BSTs with exactly `n` nodes and unique values from `1` to `n`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer `n` |
| Output | List of root nodes of all unique BSTs |
| Values used | Every value from `1` to `n` |
| Value reuse | Not allowed |
| Order | The returned list may be in any order |

Function shape:

```python
class Solution:
    def generateTrees(self, n: int) -> list[Optional[TreeNode]]:
        ...
```

## Examples

Example 1:

```python
n = 3
```

The values are:

```python
1, 2, 3
```

There are five unique BSTs:

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

So the output contains these five tree roots.

Example 2:

```python
n = 1
```

There is only one tree:

```python
1
```

So the output contains one root node.

## First Thought: Try Every Tree Shape

We could try to build every possible binary tree shape with `n` nodes, then check whether values `1..n` can be assigned to make it a BST.

That is awkward.

The BST property gives us a much cleaner construction.

If we choose a root value, then the values that go left and right are forced.

For example, if:

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

then:

```python
left subtree values  = [1, 2]
right subtree values = [4, 5]
```

So the problem splits into two smaller independent problems.

## Key Insight

For any range of values:

```python
start, start + 1, ..., end
```

we can generate all BSTs using exactly those values.

Define:

```python
build(start, end)
```

to return all BST roots that can be built from values in the range `[start, end]`.

If we choose `root_value` as the root:

```python
start <= root_value <= end
```

then:

```python
left subtrees  = build(start, root_value - 1)
right subtrees = build(root_value + 1, end)
```

Then combine every left subtree with every right subtree.

This is a divide and conquer tree generation problem.

## Empty Subtree Case

The base case is important.

If:

```python
start > end
```

there are no values left.

That means the only possible subtree is an empty subtree.

So we return:

```python
[None]
```

This may look strange at first, but it makes combinations simple.

For example, if root is `1` in the range `[1, 3]`, the left side is empty:

```python
build(1, 0) -> [None]
```

The right side contains values `[2, 3]`.

We still need to combine:

```python
left = None
right = some valid right subtree
```

Returning `[None]` lets the nested loops handle this case naturally.

## Algorithm

Call:

```python
build(1, n)
```

Inside `build(start, end)`:

1. If `start > end`, return `[None]`.
2. Create an empty result list.
3. Try each value `root_value` from `start` to `end`.
4. Generate all left subtrees from `[start, root_value - 1]`.
5. Generate all right subtrees from `[root_value + 1, end]`.
6. For every pair `(left, right)`, create a new root node.
7. Attach `left` and `right`.
8. Add the root to the result.
9. Return the result.

## Walkthrough

Use:

```python
n = 3
```

We call:

```python
build(1, 3)
```

Try root `1`.

Left side:

```python
build(1, 0) -> [None]
```

Right side:

```python
build(2, 3)
```

The range `[2, 3]` can produce:

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

So root `1` gives two trees:

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

Try root `2`.

Left side:

```python
build(1, 1) -> [1]
```

Right side:

```python
build(3, 3) -> [3]
```

So root `2` gives one tree:

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

Try root `3`.

Left side:

```python
build(1, 2)
```

The range `[1, 2]` can produce:

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

Right side:

```python
build(4, 3) -> [None]
```

So root `3` gives two trees:

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

Total:

```python
2 + 1 + 2 = 5
```

## Correctness

The algorithm creates only valid BSTs.

For each chosen root value, every value in the left range is smaller than the root, and every value in the right range is greater than the root. By recursion, every generated left subtree and right subtree is already a valid BST. Attaching them to the root therefore creates a valid BST.

The algorithm uses every value exactly once. The root uses `root_value`, the left subtree uses exactly the values from `start` to `root_value - 1`, and the right subtree uses exactly the values from `root_value + 1` to `end`. These ranges are disjoint and together contain all values from `start` to `end`.

Every valid BST over `[start, end]` has some root value `root_value`. The BST property forces all smaller values into the left subtree and all larger values into the right subtree. The algorithm tries that root value and recursively generates every possible valid left and right subtree. Therefore, it will generate that BST.

No duplicate tree is generated because each tree has one root value, one left subtree, and one right subtree. The algorithm creates each such combination exactly once.

Therefore, `build(1, n)` returns exactly all structurally unique BSTs using values `1..n`.

## Complexity

Let:

```python
C_n
```

be the `n`-th Catalan number, which counts the number of unique BSTs with `n` distinct ordered values.

The output itself contains `C_n` trees, and each tree has `n` nodes.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n * C_n)` | The algorithm must construct `C_n` trees with `n` nodes each |
| Space | `O(n * C_n)` | The returned output stores all generated trees |
| Recursion depth | `O(n)` | A tree can be fully skewed |

For `n <= 8`, this is small enough.

## Implementation

```python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def generateTrees(self, n: int) -> list[Optional[TreeNode]]:
        def build(start: int, end: int) -> list[Optional[TreeNode]]:
            if start > end:
                return [None]

            trees = []

            for root_value in range(start, end + 1):
                left_trees = build(start, root_value - 1)
                right_trees = build(root_value + 1, end)

                for left in left_trees:
                    for right in right_trees:
                        root = TreeNode(root_value)
                        root.left = left
                        root.right = right
                        trees.append(root)

            return trees

        return build(1, n)
```

## Code Explanation

The helper function represents one value interval:

```python
def build(start: int, end: int) -> list[Optional[TreeNode]]:
```

If the interval is empty, return a list containing one empty subtree:

```python
if start > end:
    return [None]
```

Then try every value as the root:

```python
for root_value in range(start, end + 1):
```

Generate every possible left subtree:

```python
left_trees = build(start, root_value - 1)
```

Generate every possible right subtree:

```python
right_trees = build(root_value + 1, end)
```

Combine every pair:

```python
for left in left_trees:
    for right in right_trees:
```

Create a fresh root node for each pair:

```python
root = TreeNode(root_value)
root.left = left
root.right = right
trees.append(root)
```

The fresh root matters because each output tree needs its own root object.

Finally, return all trees for this interval:

```python
return trees
```

The full answer is:

```python
return build(1, n)
```

## Testing

LeetCode compares tree structures. For local tests, serialize each tree in level order and compare the set of serializations.

```python
from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def serialize(root):
    if root is None:
        return []

    result = []
    queue = deque([root])

    while queue:
        node = queue.popleft()

        if node is None:
            result.append(None)
            continue

        result.append(node.val)
        queue.append(node.left)
        queue.append(node.right)

    while result and result[-1] is None:
        result.pop()

    return result

def run_tests():
    s = Solution()

    trees = s.generateTrees(1)
    assert [serialize(tree) for tree in trees] == [[1]]

    trees = s.generateTrees(2)
    assert sorted(serialize(tree) for tree in trees) == sorted([
        [1, None, 2],
        [2, 1],
    ])

    trees = s.generateTrees(3)
    assert len(trees) == 5
    assert sorted(serialize(tree) for tree in trees) == sorted([
        [1, None, 2, None, 3],
        [1, None, 3, 2],
        [2, 1, 3],
        [3, 1, None, None, 2],
        [3, 2, None, 1],
    ])

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `n = 1` | Smallest valid input |
| `n = 2` | One root with empty left, one root with empty right |
| `n = 3` | Main example with five trees |
| Serialization comparison | Checks structure and values |