Unique Binary Search Trees Solution

Problem

Given an integer n, count how many structurally distinct binary search trees can be built using each of the values 1 through n exactly once. Two trees are structurally different if their shapes differ or the same positions hold different values.

For n = 3, one of the five valid BSTs looks like this:

[2,1,3]

Input: n = 3
Output: 5
Explanation: With root = 2, there is one left structure and one right structure; with root = 1 or root = 3, the remaining two nodes can only stack one way, giving two trees each.

For n = 1 the answer is 1; for n = 2 the answer is 2 (one tree with the smaller value as root, one with the larger).

Intuition

When you fix which value becomes the root, the left subtree must hold all smaller values and the right subtree all larger ones — but the number of valid arrangements depends only on how many values are on each side, not which values they are. A BST built from {3, 5, 7} has the same structural count as one built from {1, 2, 3}, because BST shape is determined purely by relative order. This lets us reduce a 2D "range" problem to a 1D "count" problem and build the answer incrementally from smaller solved sizes.

Approach 1 — Brute Force Recursion

For each size n, try every value as the root. The left subtree gets (root−1) nodes and the right gets (n−root) nodes; multiply those counts together. Summing over all root choices gives the total for size n. This directly implements the Catalan recurrence but recomputes the same sizes repeatedly.

Base case: zero or one node has exactly one BST structure — return 1.
For each root value from 1 to numNodes, recursively count valid left subtrees with (root−1) nodes.
Recursively count valid right subtrees with (numNodes−root) nodes.
Add the product of both counts to a running total.
Return the total after trying all root choices.

1def numTrees(n: int) -> int:
2    def count_trees(num_nodes: int) -> int:
3        if num_nodes <= 1:
4            return 1
5        total = 0
6        for root in range(1, num_nodes + 1):
7            left_count = count_trees(root - 1)
8            right_count = count_trees(num_nodes - root)
9            total += left_count * right_count
10        return total
11
12    return count_trees(n)

Time: O(Catalan(n)) ≈ O(4^n / n^1.5) — every unique subproblem is recomputed from scratch on each call, giving exponential growth.
Space: O(n) — recursion stack depth equals n.

Approach 2 — Dynamic Programming

Build answers bottom-up. dp[i] holds the count of unique BSTs with exactly i nodes. Each dp[i] is the sum of dp[root−1] * dp[i−root] for every possible root. Every sub-answer is computed once and reused in O(1), reducing exponential work to polynomial.

Allocate dp of size n+1, initialized to 0.
Set dp[0] = 1 — the empty tree is one valid subtree structure (needed when a node has no left or right child).
For each size from 2 to n, try every root from 1 to size.
Add dp[root-1] * dp[size-root] to dp[size] — left count times right count.
Return dp[n].

1def numTrees(n: int) -> int:
2    dp = [0] * (n + 1)
3    dp[0] = 1  # empty tree is one valid subtree structure
4
5    for num_nodes in range(1, n + 1):
6        for root in range(1, num_nodes + 1):
7            # left subtree has (root-1) nodes, right has (num_nodes-root)
8            dp[num_nodes] += dp[root - 1] * dp[num_nodes - root]
9
10    return dp[n]

Time: O(n²) — two nested loops each up to n.
Space: O(n) — the dp array stores one count per size.

Complexity Summary

Approach	Time	Space	When to use
Brute Force Recursion	O(Catalan(n))	O(n)	Only for tracing the recurrence by hand — too slow for n > ~15
Dynamic Programming	O(n²)	O(n)	Always; n ≤ 19 per constraints, so this runs in microseconds

Common Mistakes

Setting dp[0] = 0 instead of 1 — The empty tree must count as one valid structure; if it's 0, every product in the recurrence becomes 0 and all results collapse to 0.
Using dp[root] * dp[numNodes - root - 1] instead of dp[root-1] * dp[numNodes-root] — Root is 1-indexed, so the left subtree holds exactly (root−1) nodes; shifting the index by one here produces wrong counts for every size.
Thinking values matter, not just counts — A BST built from {5, 7, 11} has the same structural options as one built from {1, 2, 3}; relative order is all that determines shape, so dp needs only one dimension.
Hardcoding dp[1] = 1 as a special case — dp[1] falls out correctly from the formula when dp[0] = 1, so only dp[0] needs manual initialization; adding a separate dp[1] = 1 isn't wrong but obscures why the base case is dp[0].
Confusing this with "Generate Binary Search Trees" (LeetCode 95) — That problem returns all actual tree structures, requiring O(Catalan(n)) space to hold them; this problem only counts them and needs O(n).

Unique Binary Search Trees — Solution