Unique Binary Search Trees
Unique Binary Search Trees: count the structurally distinct BSTs that store exactly the values 1 through n.
- 1 <= n <= 19
Intuition
Pick any value as the root. Everything smaller must form its left subtree and everything larger its right, so the two sides are independent — multiply their counts. Summing that product over every possible root gives the total, and only the sizes of the subtrees matter, never the actual values.
Choosing a root and multiplying independent sub-counts is the Catalan signature — it appears in Unique Binary Search Trees II, Generate Parentheses, and polygon triangulation. The tell is a structure that splits into two independent halves whose sizes sum to n−1.
Approach
Before reading on: fix the root at value k. How many values must sit on its left, and how many on its right? Then ask whether the answer depends on which values those are. Aim for O(n²).
Choosing a root splits the problem
If the root is k, then values 1 … k-1 occupy the left subtree and k+1 … n the right. The BST ordering forces this split completely — there is no freedom about which values go where. The two subtrees can then be arranged independently, so the number of trees with root k is the product of the counts for a left subtree of size k-1 and a right subtree of size n-k.
Only size matters, which makes the DP work
The count for a set of values depends solely on how many there are, not which they are: any 3 consecutive values arrange into the same number of shapes as any other 3. That is what allows a one-dimensional table. Let dp[i] be the count for i nodes; then dp[i] = Σ dp[j] * dp[i-1-j] for j from 0 to i-1, where j is the left subtree's size. Seed dp[0] = 1, since the empty tree is one valid arrangement — and that seed is what makes the products come out right at the edges.
These are the Catalan numbers
The recurrence is precisely the Catalan convolution, so the answers run 1, 1, 2, 5, 14, 42, 132 — the same sequence that counts balanced parenthesisations and triangulations of a polygon. The DP fills an n×n triangle of products in O(n²) time and O(n) space. A closed form, C(2n, n) / (n+1), computes it in O(n), though the DP is what an interviewer is usually looking for.
Solution & live demo
Common pitfalls
Setting dp[0] to 0
dp[0] = 0
dp[0] = 1
An empty subtree is one valid arrangement, not zero. With 0 every product involving an empty side collapses and the whole table stays 0.
Getting the subtree sizes wrong
dp[nodes] += dp[left] * dp[nodes - left]
dp[nodes] += dp[left] * dp[nodes - 1 - left]
The root itself consumes one node, so the two subtrees hold left and nodes - 1 - left values. Forgetting the root overcounts and reads past the intended entries.
Adding instead of multiplying
dp[nodes] += dp[left] + dp[nodes - 1 - left]
dp[nodes] += dp[left] * dp[nodes - 1 - left]
The subtrees are independent, so every left arrangement pairs with every right one — a product. Adding counts them as alternatives rather than combinations.
Edge cases
The empty tree counts as one arrangement, so dp[0] = 1.
A single node forms exactly one tree.
Either value can be the root, giving 2.
The classic answer of 5, which is the first non-obvious case.
The result is 1,767,263,190 — within 32-bit range, but only just.