正解は「イ」です。
2分探索木とは、「ある節点の左の子(およびその子孫)に含まれる値はすべてその節点よりも小さく、右の子(およびその子孫)に含まれる値はすべてその節点よりも大きい」 という規則がすべての節点で成り立つ2分木です。
各選択肢を検証します:
- ア: 根 16 の左部分木にある節点 15 の右の子が 14 になっています。右の子は親よりも大きい必要がありますが、14 < 15 なので規則に反します。
- イ: 根 17 に対し、左部分木は {14, 10, 16}、右部分木は {19, 18} です。節点 14 は左の子 10 と右の子 16 をもち 10 < 14 < 16 を満たし、いずれも根 17 より小さいです。節点 19 は左の子 18 をもち 18 < 19 を満たし、いずれも根 17 より大きいです。すべての節点で規則が成り立っています。
- ウ: 根 18 の左部分木にある節点 16 の右の子が 14 になっています。14 < 16 なので規則に反します。
- エ: 根 20 の右の子が 19 になっています。右の子は親よりも大きい必要がありますが、19 < 20 なので規則に反します。
したがって、2分探索木になっているのは「イ」です。