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.
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.
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 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.
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.
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.