Number of Binary Search Tree with height 4 How many Binary Search trees have 6 nodes with a depth of 4?
If I try to create them manually one by one, then there is a chance that I may miss some of the Binary Search trees, please suggest some approach to solve this kind of questions.
PS: I know that with $n$ distinct numbers, total possible Binary Search Trees are $$\frac{1}{n+1} \binom{2n}{n}.$$
[edit]
I am getting only 8 Binary Search Trees as shown in the following picture :
8 possible Binary Search trees
 A: Having a height of 4 means that 5 of the nodes form a line, the "trunk". The only remaining variation is where the remaining node connects to the trunk. It cannot connect to the lowest trunk node, because that would increase the tree height to 5. So there are exactly 4 choices where it could connect:
$\begin{align}&\bullet - \bullet - \bullet - \bullet - \bullet \\&|\\&\bullet\end{align}$
$\begin{align}\bullet - &\bullet - \bullet - \bullet - \bullet \\&|\\&\bullet\end{align}$
$\begin{align}\bullet - \bullet - &\bullet - \bullet - \bullet \\&|\\&\bullet\end{align}$
$\begin{align}\bullet - \bullet - \bullet - &\bullet - \bullet \\&|\\&\bullet\end{align}$
Now multiply that by the $6!$ ways to assign $1$ thru $6$ to the 6 nodes.
Edit
The above wrongly considers unordered trees, but "Binary Trees" are ordered. There are two ways to assign the final node to each of the trunk nodes (except the last to which it cannot be attached). Thus there are 8 possible unlabeled trees.
Also the problem statement was changed after I posted. The original statement was about labeled trees. Thus the comment about at the end about assigning labels no longer applies.
