Unique Binary Search Trees

The shape is what you count; BST ordering is what makes each root split deterministic.

A direct recursive solution tries every value as the root, recursively counts the left and right subtrees, and repeats the same subtree counts many times. The dynamic programming solution keeps the useful decomposition:

1. Choose a root rank.
2. Count the possible left-subtree structures.
3. Count the possible right-subtree structures.
4. Multiply those independent counts.
5. Sum over every possible root.

That gives an O(n²) one-dimensional DP solution. The detail that makes the recurrence work is easy to miss: an empty subtree contributes one structure, not zero.

Read the counting contract

Given n, count the structurally unique binary search trees containing the distinct values 1 through n.

The output is a count. You do not construct the trees or return their roots.

For small inputs:

• n = 1 produces 1.
• n = 2 produces 2.
• n = 3 produces 5.

For n = 2, the two structures are:

1          2
 \        /
  2      1

The labels matter because they enforce the BST ordering, but they do not require a separate DP dimension. Once the root rank is chosen, the values assigned to the left and right subtrees are forced.

A subtree containing {1, 2, 3} has the same number of possible structures as a subtree containing {8, 9, 10}. Relabeling one ordered consecutive set to the other preserves every < and > relationship. Therefore, the number of valid structures depends only on the number of nodes, not on the specific consecutive labels.

That is the state compression:

dp[k] = number of structurally unique BSTs formed from k consecutive values

The state counts structures over an ordered value set. It is not counting arbitrary binary-tree shapes detached from the BST rule.

Derive the root recurrence

Suppose we want to count BSTs with i nodes.

Every nonempty BST has exactly one root. Choose that root by rank rather than by its literal value.

If j nodes are placed in the left subtree:

• The root is the (j + 1)th smallest value.
• The left subtree contains j nodes.
• The root consumes one node.
• The right subtree contains i - j - 1 nodes.

The root-rank mapping is direct:

left_size	Root rank	Root value for values 1..3
0	1st	1
1	2nd	2
2	3rd	3

The actual values on each side are not choices. BST ordering forces the j smaller values left and the remaining larger values right.

For a fixed root split, the left and right structures can be chosen independently. If there are dp[j] possible left structures and dp[i - j - 1] possible right structures, then the number of complete trees for that root is:

dp[j] * dp[i - j - 1]

The multiplication counts every possible left-right pairing. If the left side has two choices and the right side has three, there are six complete pairings.

Summing over every legal left-subtree size gives:

$$ dp[i] = \sum_{j=0}^{i-1} dp[j] \cdot dp[i-j-1] $$

For i = 3:

Left nodes j	Root value	Right nodes	Contribution
0	1	2	dp[0] * dp[2]
1	2	1	dp[1] * dp[1]
2	3	0	dp[2] * dp[0]

This is the structural-count pattern worth recognizing: enumerate a unique top-level choice, count independent components, multiply their possibilities, and sum disjoint cases.

Set the empty tree to one

The recurrence needs a value for dp[0], even though the input constraint starts at n = 1.

Set:

dp[0] = 1

There is exactly one way to form an empty subtree: choose no nodes.

This is not a cosmetic convention. It is the multiplicative identity required by the decomposition.

A one-node tree has:

• One empty left subtree.
• One empty right subtree.

So the recurrence must produce:

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

The empty side contributes no additional structural choice, but it must still allow the other side and the root to form a valid tree.

If dp[0] were initialized to 0, every root with an empty child would contribute zero:

dp[0] * dp[2] = 0
dp[1] * dp[0] = 0

That would erase valid skewed trees. A bad empty-case definition does not stay confined to n = 0; it poisons every larger state that touches an empty side.

The first states are:

i	Contributions	dp[i]
0	empty structure	1
1	dp[0] * dp[0] = 1	1
2	dp[0] * dp[1] + dp[1] * dp[0] = 1 + 1	2
3	dp[0] * dp[2] + dp[1] * dp[1] + dp[2] * dp[0] = 2 + 1 + 2	5

The resulting sequence begins:

1, 1, 2, 5, 14, ...

These are Catalan numbers, so this is often called Catalan number DP. That label is useful as a recognition signal, but it should come after the derivation. Memorizing the sequence does not explain why the root split produces it.

Base-case invariant: dp[0] = 1 represents one valid way to complete a missing child. It lets multiplication model independent subtree choices without deleting trees that have an empty side.

Prove that the count is exact

The recurrence is only useful if it counts every valid tree once—neither missing trees nor duplicating them.

Every valid tree belongs to a root case

Take any nonempty BST with i nodes. It has one root. If that root has j nodes in its left subtree, the tree belongs to the term:

dp[j] * dp[i - j - 1]

Because the tree is a BST, all smaller values must be on the left and all larger values must be on the right. The root has some rank from 1 through i, so every valid tree appears in at least one case.

Root cases do not overlap

A tree has exactly one root value and therefore exactly one root rank. It cannot be counted under two different root cases.

The sum therefore combines mutually exclusive cases.

Each pairing creates exactly one tree

Fix a root rank. Choose one valid left structure and one valid right structure.

The root value is fixed by its rank. The values assigned to each side are fixed by BST ordering. Attaching the two chosen structures below that root creates exactly one full BST.

Conversely, changing the left structure changes the full tree, and changing the right structure also changes the full tree. Therefore, the number of full trees for this root is exactly the product of the two subtree counts.

Induction on node count

A formal induction makes the dependency clear:

• Base case: dp[0] = 1 correctly counts the empty subtree.
• Inductive assumption: every state for fewer than i nodes is correct.
• Inductive step: each i-node tree has one root split. Its left and right subtrees have fewer than i nodes, so their counts are correct by assumption. Multiplication counts every pairing for that root, and summing all root ranks counts every i-node tree exactly once.

Thus dp[i] is correct for every i, and dp[n] is the required answer.

The proof has two essential ingredients:

1. Unique decomposition: each complete tree has one root split.
2. Independent reconstruction: every valid left-right pair reconstructs one complete tree.

Remove either property and the product-and-sum recurrence is no longer justified.

Implement bottom-up Python DP

The recursive definition is natural, but naïve recursion recomputes the same subtree counts. Memoization would remove that repetition. Bottom-up tabulation makes the dependency order explicit: every state needed for dp[node_count] has a smaller index and is already available.

class Solution:
    def numTrees(self, n: int) -> int:
        # dp[k] = number of structurally unique BSTs with k nodes
        dp = [0] * (n + 1)
        dp[0] = 1

        for node_count in range(1, n + 1):
            for left_size in range(node_count):
                right_size = node_count - left_size - 1
                dp[node_count] += dp[left_size] * dp[right_size]

        return dp[n]

Each variable satisfies a specific obligation from the derivation:

• node_count is the size of the tree currently being counted.
• left_size enumerates every possible root rank indirectly.
• right_size accounts for all nodes remaining after the left subtree and root.
• dp[left_size] * dp[right_size] counts all independent left-right pairings.

The inner loop uses:

range(node_count)

so left_size takes every value from 0 through node_count - 1. These are exactly the legal left-subtree sizes. The resulting right_size is always nonnegative.

No TreeNode objects are needed. The output contract asks for a number, so storing counts is the correct abstraction. Constructing the trees would solve a different problem and would pay the cost of materializing every result.

Dry run for n = 3

Initialize:

dp = [1, 0, 0, 0]

For one node, left_size = 0, so the root has rank 1:

dp[1] += dp[0] * dp[0]
dp[1] = 1

For two nodes:

left_size = 0  -> root rank 1 -> dp[0] * dp[1] = 1
left_size = 1  -> root rank 2 -> dp[1] * dp[0] = 1
dp[2] = 2

For three nodes:

left_size = 0  -> root rank 1 -> dp[0] * dp[2] = 2
left_size = 1  -> root rank 2 -> dp[1] * dp[1] = 1
left_size = 2  -> root rank 3 -> dp[2] * dp[0] = 2
dp[3] = 5

The middle root produces one balanced structure. Each outer root leaves a two-node subtree, which can take two shapes. The total is:

2 + 1 + 2 = 5

The dry run is valuable because it exposes the rank mapping and the two boundary cases. It does more work than simply asserting that the answer is five.

Analyze time, space, and integer growth

For each tree size i, the algorithm tests i possible root splits. The total number of inner-loop iterations is:

$$ 1 + 2 + 3 + \dots + n = O(n^2) $$

The DP array contains n + 1 integers, so the auxiliary space is:

$$ O(n) $$

This is the useful one-dimensional compression. Each state depends on many earlier states, so constant space is not available for this recurrence without replacing the derivation with a different mathematical computation.

The values are Catalan numbers:

$$ C_n = \frac{1}{n+1}\binom{2n}{n} $$

A closed-form or multiplicative Catalan computation may reduce the number of state transitions, but it is usually a weaker first explanation in an interview. The recurrence shows why the tree count has this form. The formula only identifies the resulting sequence.

The count grows quickly. Python integers support arbitrary-precision arithmetic, so the implementation directly represents the mathematical result. In a language with fixed-width integer types, verify that the selected type can hold the required answer. If the constraint is generalized beyond the stated range, integer size may become part of the implementation design rather than a footnote.

Keep the output distinction explicit:

• Counting structures: store one integer for each subtree size.
• Generating structures: store or materialize every tree.

The number of structures grows rapidly, so a generation problem has output-size costs that this count-only DP deliberately avoids.

Check boundaries and transfer the pattern

Use a compact verification pass before submitting:

• n = 1 must return 1.
• n = 2 must return 2, including both skewed structures.
• n = 3 must return 5, with contributions 2 + 1 + 2.
• dp[0] must start at 1.
• The inner loop must include both left_size = 0 and left_size = node_count - 1.
• The root must be counted exactly once through node_count - left_size - 1.

Do not multiply by an additional label-arrangement factor. The values are already fixed as 1 through n, and BST ordering determines which consecutive values belong on each side of the chosen root.

The decision boundary is equally important: this DP is the right abstraction when the output is a count. If the output changes to “return every unique BST,” the recurrence remains useful, but each dp[k] must hold collections of structures instead of one integer. That changes memory, runtime, and implementation strategy substantially.

Interview recognition rule: When a recursive object has one unique top-level choice that divides it into independent components, enumerate that choice, multiply the component counts, and sum the disjoint cases.

Here, the top-level choice is the root rank. The components are the left and right subtrees. The empty component has one valid completion. Compute smaller sizes first, then let the recurrence carry the proof.

Find the split. Name the state. Get the empty case right. Then make the code follow the decomposition exactly.