Introduction

The number of different binary search trees that can be formed from n distinct keys is a classic counting problem. It shows up in data structures, recursion, and combinatorics, and the answer is one of the most famous integer sequences in mathematics: the Catalan numbers.

If the keys are distinct, then the shape of the BST is completely determined by which key becomes the root, which keys fall into the left subtree, and which keys fall into the right subtree. That structure gives us both an intuitive explanation and an efficient way to compute the answer.

Why Catalan Numbers Appear

Suppose the keys are 1, 2, ..., n. If we choose key k as the root:

• the left subtree must use the k - 1 smaller keys
• the right subtree must use the n - k larger keys

The important point is that the left and right choices are independent. So if there are:

• count(k - 1) possible left subtrees
• count(n - k) possible right subtrees

then choosing k as the root contributes:

• count(k - 1) * count(n - k)

possible BSTs.

Adding that over every possible root gives the recurrence:

• count(n) = sum from k = 1 to n of count(k - 1) * count(n - k)

with the base case:

• count(0) = 1

That 1 may feel strange at first, but it means there is exactly one empty subtree. We need that base case so leaf configurations multiply correctly.

This recurrence is exactly the Catalan recurrence, so:

• count(n) = C_n

and the closed form is:

• C_n = (1 / (n + 1)) * binom(2n, n)

Small Example with n = 3

Let the keys be 1, 2, 3.

If 1 is the root:

• the left subtree is empty
• the right subtree must be a BST built from 2, 3
• that gives 2 possibilities

If 2 is the root:

• the left subtree must contain 1
• the right subtree must contain 3
• that gives 1 possibility

If 3 is the root:

• this mirrors the case where 1 is the root
• that gives 2 possibilities

So the total is:

• 2 + 1 + 2 = 5

That matches the third Catalan number:

• C_3 = 5

The first few values are:

• count(0) = 1
• count(1) = 1
• count(2) = 2
• count(3) = 5
• count(4) = 14
• count(5) = 42

Dynamic Programming Solution

The recurrence is simple, but a naive recursive implementation repeats the same subproblems many times. Dynamic programming is the cleaner way to compute the count.

1def count_bsts(n: int) -> int:
2    dp = [0] * (n + 1)
3    dp[0] = 1
4
5    for nodes in range(1, n + 1):
6        total = 0
7        for root in range(1, nodes + 1):
8            left_size = root - 1
9            right_size = nodes - root
10            total += dp[left_size] * dp[right_size]
11        dp[nodes] = total
12
13    return dp[n]
14
15
16for n in range(6):
17    print(n, count_bsts(n))

This prints:

10 1
21 1
32 2
43 5
54 14
65 42

The time complexity is O(n^2) because for each nodes value, we try every possible root. The space complexity is O(n).

Closed-Form Formula

If you only need the final count and not the recurrence itself, the Catalan formula is compact:

• C_n = factorial(2n) / (factorial(n + 1) * factorial(n))

In Python:

1from math import comb
2
3
4def count_bsts_closed_form(n: int) -> int:
5    return comb(2 * n, n) // (n + 1)
6
7
8print(count_bsts_closed_form(5))  # 42

This is mathematically elegant, but the dynamic-programming version is often better for teaching because it shows why the formula works.

Common Mistakes

One common mistake is forgetting the empty-tree base case. If you use count(0) = 0, every count will collapse incorrectly because leaf combinations depend on multiplying by 1, not 0.

Another mistake is confusing the number of BSTs with the number of binary trees. The BST property matters because the inorder ordering of the keys is fixed. Once the root is chosen, the left subtree must contain the smaller keys and the right subtree must contain the larger ones.

It is also easy to think the actual key values matter. They do not, as long as the keys are distinct and totally ordered. The count depends only on n, not on whether the keys are 1, 2, 3 or 10, 50, 90.

Finally, be careful with recursion-only implementations for larger n. They are correct in principle, but inefficient without memoization.

Why This Problem Matters

This question is more than a puzzle. It is a good example of a recursive counting argument:

• choose a root
• split the problem into smaller independent pieces
• multiply the independent choices
• sum over all root positions

That pattern appears in many algorithmic counting problems, especially when recursive structure is involved.

Summary

• The number of BSTs over n distinct keys is the nth Catalan number.
• The recurrence is count(n) = sum count(left) * count(right) over all root choices.
• The base case count(0) = 1 is essential.
• For n = 3, the answer is 5.
• Dynamic programming computes the answer in O(n^2) time and O(n) space.