解説資料の7ページ目の奇数の場合の式
n^(k-1)*nじゃないですか?

間違いでした。後程訂正します。

二分探索木の定義を教えて下さい

確認中ですが、図のような木を構成する問題だと解釈してください。