Unique Binary Search Trees: Catalan Numbers and DP

Given an integer n, return the number of structurally unique BSTs that contain exactly n nodes with unique values from 1 to n.

This is LeetCode 96: Unique Binary Search Trees, and it connects two powerful ideas: the Catalan number sequence and dynamic programming. At first glance it looks like a combinatorics puzzle, but the solution is a clean DP loop that builds on the same principles you have seen in other DP problems.

For n = 3, there are exactly 5 unique BSTs. For n = 1, there is 1. These counts follow the Catalan number sequence: 1, 1, 2, 5, 14, 42, ...

Why this problem matters

This problem forces you to think about a different kind of substructure than the usual linear DP. Instead of building a solution left to right along an array, you are splitting a set of values around a chosen root and combining results from the left and right halves. That root-splitting pattern shows up in many tree problems.

The key observations are:

• Root choice determines the split. If you pick value i as the root, then values 1 through i-1 go into the left subtree and values i+1 through n go into the right subtree.
• Structure depends only on count, not on actual values. A left subtree with 2 nodes has the same number of structural arrangements regardless of which specific values fill it. So dp[k] only depends on how many nodes are in the subtree, not which ones.
• Left and right are independent. The number of trees you can form equals the product of left subtree arrangements times right subtree arrangements.

The recurrence

Define dp[n] as the number of structurally unique BSTs with n nodes. For each possible root i from 1 to n:

• Left subtree has i - 1 nodes, giving dp[i - 1] arrangements
• Right subtree has n - i nodes, giving dp[n - i] arrangements
• These combine as a product: dp[i - 1] * dp[n - i]

Sum over all root choices:

dp[n] = dp[0]*dp[n-1] + dp[1]*dp[n-2] + ... + dp[n-1]*dp[0]

This is exactly the Catalan number recurrence. The base cases are dp[0] = 1 (an empty tree is one valid structure) and dp[1] = 1 (a single node has one arrangement).

Building the DP table

Let's trace through the table for n = 3:

The pattern is clear: for each n, iterate over every root choice, multiply the left and right subtree counts, and sum the products. The answer for n = 3 is dp[3] = 5, which matches the five trees shown above.

Python solution

def num_trees(n):
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1

    for nodes in range(2, n + 1):
        for root in range(1, nodes + 1):
            dp[nodes] += dp[root - 1] * dp[nodes - root]

    return dp[n]

Time: O(n^2). Two nested loops, the outer from 2 to n and the inner from 1 to nodes.

Space: O(n). A single array of length n + 1.

Walkthrough for n = 4

To make the pattern more concrete, here is how dp[4] is computed from the values you already have:

• root = 1: left has 0 nodes, right has 3. dp[0] * dp[3] = 1 * 5 = 5
• root = 2: left has 1 node, right has 2. dp[1] * dp[2] = 1 * 2 = 2
• root = 3: left has 2 nodes, right has 1. dp[2] * dp[1] = 2 * 1 = 2
• root = 4: left has 3 nodes, right has 0. dp[3] * dp[0] = 5 * 1 = 5

Total: 5 + 2 + 2 + 5 = 14. The 4th Catalan number.

Notice the symmetry: the terms read the same forwards and backwards. This happens because choosing root i in an n-node tree gives you the mirror of choosing root n + 1 - i. The Catalan numbers always have this symmetric structure.

Complexity analysis

The DP approach is the practical choice for interviews. The closed-form involves computing large factorials or using the iterative Catalan formula C(n) = C(n-1) * 2(2n-1) / (n+1), which is O(n) time and O(1) space. But the DP version generalizes better to related problems where the closed-form does not apply.

Edge cases to watch for

• n = 0: dp[0] = 1. An empty tree is one valid structure. This base case is essential for the recurrence to work.
• n = 1: dp[1] = 1. One node, one tree.
• n = 2: dp[2] = 2. Either the smaller value is root with the larger as right child, or vice versa.

The building blocks

This problem is built on two reusable patterns:

Catalan number recurrence. The formula dp[n] = sum of dp[i-1] * dp[n-i] for i from 1 to n is the defining recurrence for Catalan numbers. It appears whenever you are counting the number of ways to split a structure into two independent halves and combine them. Beyond BSTs, the same recurrence counts the number of valid parenthesizations, the number of full binary trees, and the number of ways to triangulate a polygon.

Root-splitting DP. Choosing each possible root and combining left/right results is a tree-specific pattern. You pick a dividing element, solve the two sides independently, and multiply. This same strategy applies to:

• Unique Binary Search Trees II (LeetCode 95): instead of counting, generate all the actual trees. Same splitting logic, but you build node objects.
• Different Ways to Add Parentheses (LeetCode 241): split an expression at each operator, solve left and right halves, combine all pairs.
• Optimal Binary Search Tree: classic DP problem from CLRS using the same root-choice framework with costs.

Once you see the root-splitting pattern, these problems become variations on the same theme.

From understanding to recall

You can follow this walkthrough and see why dp[3] = 5. But can you write the two-line recurrence from scratch next week? The gap between reading a solution and reproducing it under pressure is real.

Spaced repetition closes that gap. You revisit the Catalan recurrence at increasing intervals, write the nested loop from memory, and after a few reps the pattern is automatic. The root-splitting DP pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually beats random problem grinding every time.

Related posts

• Climbing Stairs - The gentlest intro to dynamic programming, where each state depends on a fixed lookback window
• Coin Change - Another DP problem where you iterate over choices at each step and pick the best, showing the same "build from subproblems" idea