解説

2分探索木の性質を問う問題です。2分探索木は「各ノードについて、左部分木のすべての値＜そのノードの値＜右部分木のすべての値」という大小関係が、すべてのノードで成り立つ2分木です。単に「左の子＜親＜右の子」だけでなく、部分木に含まれるすべての値との大小関係が問われる点に注意して、この条件を各選択肢で検証します。イの木は、根が4で、左部分木は {2, 1, 3}（すべて4未満）、右部分木は {8, 6, 9, 5, 7}（すべて4超）です。さらにノード8の左部分木 {6, 5, 7} はすべて8未満、右の9は8超。ノード6の左の5は6未満、右の7は6超。すべてのノードで条件が成立しており、イが正解です。重要なのは「直接の子だけでなく部分木全体との大小関係」を確認することです。2分探索木では中順（左→根→右）でたどると値が必ず昇順に並ぶという性質があるので、各選択肢を中順走査して 1〜9 が昇順に現れるかを確かめる方法でも判定でき、検算としても有効です。

なぜ他の選択肢は違うのか

選択肢 ア

アの木は根が1で、その左の子が2、右の子が3です。2分探索木では左の子は親より小さくなければなりませんが、2＞1 でいきなり違反しています。最小値の1が根にある時点で、左部分木に置ける値（1未満）が存在せず、9個の値を収められません。根の値と左右の子の大小関係を見るだけで最初に除外できる選択肢です。

選択肢 ウ

ウの木は根7の左の子が6、その下に4と5があります。ノード6の右の子が5ですが、右の子は親より大きい必要があるため 5＜6 で違反です。また根7の右部分木にあるノード3（8の左の子の下）は、根7より小さい値が右部分木に存在することになり、これも違反です。部分木全体との関係まで確認する習慣があれば確実に見抜けます。

選択肢 エ

エの木は根が9で、左部分木に {7, 1, 2}、右部分木に {8, 5, 6, 3, 4} があります。右部分木の値はすべて根9より大きくなければなりませんが、8をはじめ全部が9未満で違反しています。最大値の9が根にあると右部分木に置ける値（9超）が存在しないため、構造として成立しません。根に最大値・最小値がある木は即座に疑うのがコツです。

解くときのポイント

2分探索木は「左部分木＜親＜右部分木」が全ノードで成立。直接の子だけでなく部分木全体を確認し、中順走査で昇順になるかをチェックすると確実。