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:

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

Function shape:

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

Examples

Example 1:

n = 3

There are five unique BSTs:

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

Answer:

5

Example 2:

n = 1

There is only one tree:

1

Answer:

1

First Thought: Choose a Root

A BST has a strong ordering rule.

If we choose a root value r, then:

For example, if:

n = 5
root = 3

then the left subtree must use:

[1, 2]

and the right subtree must use:

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

[1, 2, 3]

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

[4, 5, 6]

Both ranges contain three ordered values.

So define:

dp[i]

as:

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

We want:

dp[n]

Base Cases

There is one BST with zero nodes:

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:

dp[1] = 1

Recurrence

Suppose we want to compute dp[nodes].

Try each possible root position.

If the root has:

left_count

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

right_count = nodes - 1 - left_count

The number of trees for this root shape is:

dp[left_count] * dp[right_count]

because every left subtree can pair with every right subtree.

So:

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

for all:

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

This is the Catalan recurrence.

Algorithm

Create:

dp = [0] * (n + 1)

Set:

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:

dp[n]

Walkthrough

Use:

n = 3

Start:

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

Compute dp[2].

Possible splits:

So:

dp[2] = 2

Compute dp[3].

Possible splits:

So:

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

Answer:

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:

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

Implementation

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:

dp = [0] * (n + 1)

Set the base cases:

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

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

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

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

for left_count in range(nodes):

The remaining nodes go to the right subtree:

right_count = nodes - 1 - left_count

Add all combinations:

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

Finally, return the count for n nodes:

return dp[n]

Testing

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: