Basic Problemscountingcombinatoricstree

Count Unique BSTs

Given n distinct keys, count how many structurally different binary search trees can be built using all of them. The BST property fixes each key's relative order; only the shape is free to vary.

Do this lesson first: climbing stairs

Example input

n = 3 (keys 1, 2, 3)

Expected output

5

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

dp[i] = sum over roots r from 1 to i of dp[r - 1] × dp[i - r]

Ask which key is the root. Once root r is chosen, the BST property decides where every other key goes: the r - 1 smaller keys form the left subtree and the i - r larger keys form the right. Each subtree is a BST on fewer keys, and the left shape places no limit on the right one, so for this root the counts multiply: dp[r - 1] × dp[i - r]. Different roots give different trees, so nothing is counted twice, and the roots are added. The roots are summed, never compared, because every root yields valid trees and all of them count. Optimal BST, a classic interval problem outside this course's list, runs this same loop over the root but keeps the cheapest, a min instead of a sum; matrix chain multiplication in the interval family has the same shape.

dp[0] = 1, and it is the cell people get wrong: zero keys make exactly one tree, the empty one. It has to be 1 because it is multiplied; the smallest key as root always has an empty left subtree, and a 0 there would erase every tree rooted at it. dp[1] then falls out as dp[0] × dp[0] = 1, a single node with two empty subtrees. Every cell reads only smaller key counts, so filling left to right works.

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

dp[0] = 1, and it is the cell people get wrong: zero keys make exactly one tree, the empty one. It has to be 1 because it is multiplied; the smallest key as root always has an empty left subtree, and a 0 there would erase every tree rooted at it. dp[1] then falls out as dp[0] × dp[0] = 1, a single node with two empty subtrees. Every cell reads only smaller key counts, so filling left to right works.

i=0

i=1

i=2

i=3

i=4

1

2

5

14

count-unique-bsts.ts

1function numTrees(n) {
2 const dp = new Array(n + 1).fill(0);
3 dp[0] = 1;
4 for (let i = 1; i <= n; i++) {
5 for (let root = 1; root <= i; root++) {
6 dp[i] += dp[root - 1] * dp[i - root];
7 }
8 }
9 return dp[n];
10}

Base caseComputedBeing readAnswer

The code, the trap, the variations

count-unique-bsts.ts

1function numTrees(n) {
2 const dp = new Array(n + 1).fill(0);
3 dp[0] = 1;
4 for (let i = 1; i <= n; i++) {
5 for (let root = 1; root <= i; root++) {
6 dp[i] += dp[root - 1] * dp[i - root];
7 }
8 }
9 return dp[n];
10}

Where people go wrong

Seeding dp[0] = 0 on the grounds that no keys means no tree. The recurrence multiplies, so the zero spreads: with dp[0] = 0 and dp[1] set to 1 by hand, dp[2] = 0 × 1 + 1 × 0 = 0, although two keys plainly make two trees, and the row goes on 0, 1, 0, 1, 0, 2, 0, 5, zeroing every even count of keys.

List every BST instead of counting them.
Same split by root, but each subproblem returns a list of trees and the product becomes every pairing of a left tree with a right tree. The trees now hold real keys, so a subproblem has to say which keys (a range lo to hi) rather than how many, and the cost grows with the answer rather than with n².
Count only BSTs whose height is at most h.
The state gains a height budget, and each subtree is counted with a budget one smaller than its parent's. The split by root and the multiply-then-add shape stay exactly as they are.
Count full binary trees instead, where every node has 0 or 2 children.
An empty subtree is no longer allowed, so the base moves from dp[0] = 1 to dp[1] = 1 (a single leaf), every even node count is 0, and the split over the root only uses odd subtree sizes. The multiply-then-add over the root stays.

nth Catalan Number Count Valid Parenthesis