Question
The number of ways in which the numbers $1,2,3,4,5,6,7,8$ can be inserted in an empty binary search tree, such that the resulting tree has height $5$, is _________.
I know it is somehow similar to this, but i think my question will need different approach.
My Solution/Approach
$\Rightarrow$ First Level can be filled with $1,6,7,8$
$\Rightarrow$ Second Level can be filled with $2,5,6,7$
$\Rightarrow$ Third Level can be filled with $3,4,5,6$
$\Rightarrow$ Fourth Level can be filled with $4,5,6,7$
$\Rightarrow$ Fifth Level can be filled with $5,6,7,8$
Total number of ways = $4 \times 4...\times 4 =4^{5}$
IS my answer correct ?