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

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:

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:

Example 2:

n = 1

There is only one tree:

Answer:

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:

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:

Try every possible number of nodes in the left subtree.
Compute the number of nodes in the right subtree.
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:

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

So:

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:

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

Answer:

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

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

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:

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