10個の節（ノード）から成る次の2分木の各節に，1から10までの値を一意に対応するように割り振ったとき，節a，bの値の組合せはどれになるか。
ここで，各節に割り振る値は，左の子及びその子孫に割り振る値よりも大きく，右の子及びその子孫に割り振る値よりも小さくするものとする。
正答1
解説
正解は1です。
各節の値が、左の子孫より大きく右の子孫より小さい木は、2分探索木です。
2分探索木を中間順（左の子孫、自分、右の子孫の順）にたどると、値は小さい順に並びます。
図の根は5で、左の子が4です。
4の左には子を2つもつ節があり、この3節に1〜3が入ります。
根の右の子がaで、aには左の子がなく、右の子が1つあります。
その右の子は、左の子にb、右の子に別の節をもちます。
さらにその節の右の子に、もう1つの節があります。
根より右側の5節には、6〜10が入ります。
中間順では、左の子がないaが最初に来るので、aは6です。
次に来るのはaの右の子の左側にあるbなので、bは7です。
続いてaの右の子が8、その右の節が9、最下段の節が10です。
【選択肢別解説】
1：○ 右側の部分木を中間順にたどると、aが最小の6、bが次の7になります。
2：× aは6で正しいですが、bは8ではありません。
8はbの親の節に入ります。
3：× aは7ではありません。
aには左の子がないので、右側の部分木で最小の6が入ります。
4：× aもbも誤りです。
aは6、bは7です。
【ポイント】
2分探索木の値の割り振りは、中間順に小さい値から順に埋めていくと確実に求まります。