Unique Binary Search Trees: From Recursion to the Catalan Numbers

The problem

Given n, count how many structurally different binary search trees store the values 1 to n. For n = 3 the answer is 5. The values themselves don't matter, only how many there are on each side of the root.

The key observation

Pick a root i. Everything smaller goes left, which is i - 1 nodes, and everything larger goes right, which is n - i nodes. The left and right shapes are chosen independently, so the number of trees with root i is G(i-1) * G(n-i), where G(k) is the answer for k nodes. Summing over every root gives the recurrence. Say the word "independently" out loud: it is why you multiply instead of add.

Bottom-up DP

def num_trees(n):
    g = [0] * (n + 1)
    g[0] = g[1] = 1
    for k in range(2, n + 1):
        for root in range(1, k + 1):
            g[k] += g[root - 1] * g[k - root]
    return g[n]

This is O(n^2) time and O(n) space, and it is the answer most interviewers expect. Set g[0] = 1 on purpose: an empty subtree is exactly one shape, and getting this base case wrong is the usual bug.

The closed form

The sequence 1, 1, 2, 5, 14, 42 is the Catalan numbers, C(n) = comb(2n, n) / (n + 1). You can compute it in O(n) with the running product c = c * 2 * (2k + 1) / (k + 2). Mention it as a follow-up, but lead with the DP, because the DP shows the reasoning.

Follow-up: generate the trees

Unique BSTs II asks for the trees themselves. Recurse on a range [lo, hi], build all left and right subtrees, and combine every pair under each root. Output size grows like the Catalan numbers, so no algorithm beats that bound; memoizing ranges only saves repeated work.

How to present it


Disclosure: I work on Linkjob AI. If you want structured practice for interviews like this, AI coding interview assistant can help you rehearse and get real-time hints.