10個の節（ノード）からなる次の2分木の各節に，1から10までの値を一意に対応するように割り振ったとき，節，の値の組合せはどれになるか。ここで，各節に割り振る値は，左の子及びその子孫に割り振る値より大きく，右の子及びその子孫に割り振る値より小さくする。
出典平成28年度 春期 基本情報技術者試験 午前 問5
ア
イ
ウ
エ
二分探索木の節に割り振る値
正解は ア （a＝6、b＝7）です。 「左の子孫＜節＜右の子孫」が成り立つ2分木（2分探索木）では、 左の部分木 → 節 → 右の部分木 の順（中間順）にたどると、値が小さい順 に並びます。1〜10を中間順の位置に順に割り振ります。 根5の左側には 4 と、その下の3つの節があるので、そこに 1〜4 が入ります（中間順で 1, 2, 3, 4）。 根5の右側の部分木に 6〜10 が入ります。a は右部分木の中で最初にたどる節（左の子がない）なので 6 。 a の右の子（8）の左の子が b で、a の次にたどるので 7 。その後 8, 9, 10 と続きます。