How many trees?

First, strip away the cyber-fairy-tale nonsense. We need the number of BSTs on keys $1,2,\dots,n$ whose height is at least $h$.

Observation 1: the actual labels are basically a red herring

For a BST with keys $1..n$, once the root key is fixed to some $i$:

• the left subtree must contain exactly the keys $1..i-1$,
• the right subtree must contain exactly the keys $i+1..n$.

So the number of possibilities depends only on the sizes of the two subtrees.

If the left subtree has $l$ nodes, then the right subtree has $n-1-l$ nodes. That is the only split information that matters.

So this is a DP on subtree sizes, not on actual key values.

Observation 2: count the complement

Trying to count trees with height at least $h$ directly is annoying as hell. The standard trick is cleaner:

• count trees with height at most $k$,
• then subtract.

Define

$$dp[n][k] = \text{number of BSTs with } n \text{ nodes and height } \le k.$$

Then the answer is

$$\text{answer} = \text{all BSTs on } n \text{ nodes} - \text{BSTs with height } < h.$$

Since height is an integer, that becomes

$$\text{answer} = dp[n][n] - dp[n][h-1].$$

Why is $dp[n][n]$ the total number of BSTs? Because any tree with $n$ nodes has height at most $n$; the worst case is just a chain.

Base cases

We treat the empty tree as a valid helper object of height $0$. This makes the recurrence nice instead of cursed.

• $dp[0][k] = 1$ for every $k \ge 0$.
• $dp[n][0] = 0$ for every $n > 0$.

A non-empty tree cannot have height $0$. Pretty revolutionary stuff.

Transition

Take a BST with $n$ nodes and height at most $k$.

Suppose the left subtree has $l$ nodes. Then:

• the root is forced,
• the right subtree has $n-1-l$ nodes,
• both subtrees must have height at most $k-1$.

So the number of possibilities for this split is

$$dp[l][k-1] \cdot dp[n-1-l][k-1].$$

Summing over every possible split:

$$dp[n][k] = \sum_{l=0}^{n-1} dp[l][k-1] \cdot dp[n-1-l][k-1].$$

And that's the whole trick.

No extra combinatorial factor is needed. Once the left subtree size is $l$:

• the root key must be $l+1$,
• the left subtree gets exactly the smallest $l$ keys,
• the right subtree gets exactly the largest $n-1-l$ keys.

Each pair of left/right BSTs gives exactly one BST of size $n$.

Why this is correct

The recurrence is a bijection, which is the kind of thing DP likes and humans tolerate.

For every BST counted by $dp[n][k]$:

1. it has some root,
2. hence some left-subtree size $l$,
3. its left and right subtrees are BSTs of sizes $l$ and $n-1-l$,
4. each of those subtrees must have height at most $k-1$.

So every valid tree contributes to exactly one term in the sum.

Conversely, if you take:

• any BST with $l$ nodes and height at most $k-1$,
• any BST with $n-1-l$ nodes and height at most $k-1$,

and attach them as left/right children of the forced root, you get a unique BST with $n$ nodes and height at most $k$.

So the recurrence counts exactly the right objects.

Complexity

There are $O(nh)$ states, and each state tries all $n$ possible left-subtree sizes.

Therefore the time complexity is

$$O(n^2 h).$$

Since $h \le n \le 35$, this is tiny. You can brute-force your DP table and still have time left to laugh at the story.

Memory usage is

$$O(nh).$$

Implementation summary

1. Build dp[n][k] for all $0 \le n,k \le N$.
2. Use the base cases above.
3. Apply the split recurrence.
4. Print $dp[n][n] - dp[n][h-1].$

This is basically Catalan DP with a height cap. Same family, slightly more attitude.