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