すべての葉が同じ深さをもち，葉以外のすべての節点が二つの子をもつ2分木に関して，節点数と深さの関係を表す式はどれか。
ここで，nは節点数，kは根から葉までの深さを表す。
例に示す2分木の深さkは2である。
正答2
解説
正解は2です。
すべての葉が同じ深さにあり、葉以外の節点が必ず2つの子をもつ2分木（完全2分木）の節点数を求める問題です。
例の図では、根が1個、深さ1の節点が2個、深さ2の葉が4個あり、深さk＝2で節点数は7です。
深さiの段には2^i個の節点が並びます。
【計算】
n＝2^0＋2^1＋…＋2^kです。
等比数列の和の公式より、n＝2^(k+1)－1となります。
k＝1ならn＝3、k＝2ならn＝7、k＝3ならn＝15です。
【選択肢別解説】
1：× k＝2ではn＝7になりますが、k＝1ではn＝5となります。
実際の節点数は3なので一致しません。
2：○ 各段の節点数1、2、4、…、2^kを合計した値です。
k＝1で3、k＝2で7、k＝3で15となり、どの深さでも一致します。
3：× k＝2では7になりますが、k＝1では0×2＋4＝4となります。
実際の3と一致しません。
4：× k＝1で3、k＝2で7と一致しますが、k＝3では3×4＋1＝13となります。
実際の15と一致しないので誤りです。
【ポイント】
選択肢はすべて例のk＝2で7になるように作られています。
1つの例だけで判断せず、別の深さでも確かめることが大切です。