Algorithm for listing all binary trees of a given height

I've been trying to find an algorithm to list all binary trees of a given height $h$.

Note that I'm not trying to count them: the number of such trees is given in the OEIS (A001699).

All the algorithms that I have been able to see list all binary trees for a given number of nodes. A very inefficient way of solving the problem would proceed by checking all the trees with a number of nodes between $h+1$ and $2^{h+1}-1$, but this is not great at all.

Any pointers or references would be much appreciated.

As hinted at in comments, just follow the recursive structure of binary trees.

We create a function listbt(h) that lists all binary trees of exactly height h.

type BTree = Leaf | Node(BTree, BTree)

def listbt 0 = { [Leaf] }
| listbt h = {
result = []
for T in (listbt h-1) {
for k in (0..h-1) {
for t in (listbt k) {
result += Node(T, t)
result += Node(t, T) if k

Correctness follows with an elementary inductive proof over h.

If you memoize the results of listbt this is going to be as efficient as it gets; the sheer number of trees and thereby the number of checks t != T dominate.

Note that if you employ term sharing (i.e. only link t and T in Node(t, T) but do not copy them) you can reduce the size of the output significantly. That only makes sense if your BTree` implementation is immutable, though.

StackExchange Computer Science Q#57618, answer score: 2