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:

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:

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

Function shape:

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

Examples

Example 1:

n = 3

The values are:

1, 2, 3

There are five unique BSTs:

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:

n = 1

There is only one tree:

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:

n = 5
root = 3

then:

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:

start, start + 1, ..., end

we can generate all BSTs using exactly those values.

Define:

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:

start <= root_value <= end

then:

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:

start > end

there are no values left.

That means the only possible subtree is an empty subtree.

So we return:

[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:

build(1, 0) -> [None]

The right side contains values [2, 3].

We still need to combine:

left = None
right = some valid right subtree

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

Algorithm

Call:

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:

n = 3

We call:

build(1, 3)

Try root 1.

Left side:

build(1, 0) -> [None]

Right side:

build(2, 3)

The range [2, 3] can produce:

2      3
 \    /
  3  2

So root 1 gives two trees:

1      1
 \      \
  2      3
   \    /
    3  2

Try root 2.

Left side:

build(1, 1) -> [1]

Right side:

build(3, 3) -> [3]

So root 2 gives one tree:

  2
 / \
1   3

Try root 3.

Left side:

build(1, 2)

The range [1, 2] can produce:

1      2
 \    /
  2  1

Right side:

build(4, 3) -> [None]

So root 3 gives two trees:

    3      3
   /      /
  1      2
   \    /
    2  1

Total:

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:

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.

For n <= 8, this is small enough.

Implementation

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

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

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

if start > end:
    return [None]

Then try every value as the root:

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

Generate every possible left subtree:

left_trees = build(start, root_value - 1)

Generate every possible right subtree:

right_trees = build(root_value + 1, end)

Combine every pair:

for left in left_trees:
    for right in right_trees:

Create a fresh root node for each pair:

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:

return trees

The full answer is:

return build(1, n)

Testing

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

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: