binary-search-tree - 二分探索木のノードサイズ

Question

二分探索木でノードの順序をどのように配置できるかについて少し混乱しています。ルートノードよりも大きい左側の二分探索木にサブツリーのノードが存在する可能性はありますか？

たとえば、次は二分探索木でしょうか？

    2
   / \
  1   4
 / \
    3

上記で私を混乱させているのは、1（3）の右側のサブツリーが元のルートノード（2）よりも大きくなる可能性があるかどうかです。

Answer 1

いいえ、ルートよりも大きいノードを左側に配置することはできません。二分探索木には次のプロパティがあります（wikiから）：

1. ノードの左側のサブツリーには、ノードのキーよりも小さいキーを持つノードのみが含まれています。
2. ノードの右側のサブツリーには、ノードのキー以上のキーを持つノードのみが含まれます。
3. 左と右の両方のサブツリーも二分探索木である必要があります。