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.
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.