すべての葉の深さが等しく、葉以外の節点がすべて2つの子をもつ2分木がある。根から葉までの辺の数（高さ）が4であるとき、節点の総数はいくつか。

解説

正解は「31」です。この2分木では深さ d の節点が $2^d$ 個あるので、高さ4の節点の総数は $1+2+4+8+16=31$ 個、一般には高さ h で $2^{h+1}-1$ 個です。「16」は最も深いレベルにある葉の数 $2^4=16$ で、葉以外の節点を数えていません。「15」は葉以外の内部節点の数 $2^4-1=15$ です。「32」は $2^5$ で、1を引き忘れた値です。逆に、節点数が n のときの高さは約 ${\log }_{2}n$ となります。これが、バランスのとれた2分探索木で探索の比較回数が $O(\log n)$ になる理由です。