When trees are tall!

Let us consider the generalized problem of a tall binary tree with $n$ nodes.

To make the tree as tall as possible, we require that it has no "branches", i.e, there are no nodes which have both left and right children. This means that we have two choices, to make the entire subtree towards the right, in which case the root element is the minimum, or towards the left, in which case the root element is the maximum.

After we have made that choice, all we need to do is build a rebuild a tall tree with $n-1$ nodes and root it according to the choice we made.

So, $Trees(n) = 2 \; Trees(n-1)$

It is clear that with a single node there is only a single such tree. Hence, $Trees(1) = 1$

That gives us the general formula $Trees(n) = 2^{n-1}$ . Plugging in $10$ gives $512$ .