Number of binary search trees with maximum possible height for n nodes

Question

I'm using the definition of the height of a tree as the longest possible path from the root to a leaf by its number of edges, e.g. a tree of 2 nodes has a height of 1. With that in mind, what would be the number of binary search trees (don't have to be balanced) that have the maximum possible height for n-nodes?

So far, I know that the maximum height of any binary search tree of n-nodes is n-1 since we're counting edges. So for example, a binary search tree of 3 nodes has a maximum height of h = 3-1 = 2 and there are 4 possible trees with n-nodes that have the maximum height of 2.

I also know that for n-nodes, there are (2n)!/((n+1)!n!) possible trees.

I'm able to find this manually for trees where n is small but would like to find a formula for any n.

EDIT:
The BST definition I am working with defines a Binary Search tree as a binary tree where each node has at most 2 children and does NOT need to be nearly-complete, so you could have a tree of 3 nodes with a height of 2. It also satisfies the BST property where all nodes in the left subtree of a node x has keys smaller than x's key and all nodes in the right subtree of a node x has keys larger than x's key.

• Yuval Filmus: Have you plugged in the values you've found for small $n$ in the Online Encyclopedia of Integer Sequences?
• Yuval Filmus: In a binary search tree, every internal node has two children. In particular there is no binary search tree with only two nodes. A binary search tree with three nodes has height 1, and in general the maximum height of a binary search tree with $n$ nodes is $n-2$. There are 2ドル^{n-3}$ binary trees of this height, since at every internal node but the last one we choose which side is a leaf.
• Paradox: @YuvalFilmus The definition I'm working with considers a binary search tree to be a binary tree with at most 2 children, but it does not need to be nearly-complete. It also has the BST property. So I can have a 3-node tree of height 2.

Answer 1

The number of trees with $n$ nodes of height $n-1$ is 2ドル^{n-1}$. Indeed, every internal node has exactly one child, which can either be the left child or the right child. Since there are $n-1$ internal nodes, this gives 2ドル^{n-1}$ options.