Algorithm for listing all binary trees of a given height
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 &lt; h-1 || t != T
      }
    }
  }
  return result
}


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.