基本情報技術者 2019年 春期 午前（科目A） 問05

二分探索木の判定【午前解説】

正解の理由

• 根 4：左部分木の値 {1,2,3} はすべて 4 未満、右部分木の値 {5,6,7,8,9} はすべて 4 より大きい。
• ノード 2：左 1 < 2 < 3（右）で成立。
• ノード 8：左部分木 {5,6,7} はすべて 8 未満、右は 9 > 8 で成立。
• ノード 6：左 5 < 6 < 7（右）で成立。

解法ステップ

1. 定義を確認する：「任意のノードに対して左部分木の全値 < ノードの値 < 右部分木の全値」。
2. 手早いチェック法1（試験向け）: 中間順（in-order）走査を紙上で行い、出力が厳密に昇順かを確認する。
3. 手早いチェック法2（厳密）: 根から再帰的に許容される最小値・最大値の範囲を維持しながら各ノードを検証する（min/max 法）。
4. 計算量: いずれも O(n)（n はノード数）で判定可能。中間順走査は一度で全順序を確認できるため実務・試験ともに有効。

選択肢別の誤答解説

• ア：根が 1 で、左子に 2 があるため即違反。左部分木の値が根より大きいので BST の条件に反します。
• イ：正解。上記の通り、すべてのノードで左部分木 < ノード < 右部分木 が成り立ち、中間順走査が 1..9 の昇順になります。
• ウ：一見局所的には成り立つ箇所もありますが、根 7 の右部分木に値 3（8 の左子）が含まれており、3 < 7 であるため「右部分木の値はすべて 7 より大きい」という条件に違反します。
• エ：根が 9 ですが右子が 8（9 より小さい）になっており、右部分木に根より小さい値があるため即違反です。

よくある誤解

• 親子の大小関係だけをチェックしてしまう：親と直接の子が条件を満たしていても、部分木内のさらに深いノードが範囲を破ることがあります。
• 二分探索木 = 完全にバランスが取れている木と誤解する：形（高さ）とは独立して、値の順序性が条件です。
• 中間順走査の意味を誤る：中間順走査が昇順であれば BST、という判定を思い出せないと手早く判断できません。

補足コラム

• 中間順（in-order）走査は二分探索木の判定で強力なツールです。ノード値に重複がない場合は「中間順の出力が厳密増加」⇔「BST」で双方向に成り立ちます。
• 重複キーの扱いは実装や定義により「左 ≤ 親 < 右」や「左 < 親 ≤ 右」など変わるので、問題文での定義（通常は厳密不等号）を確認してください。
• 実装例（迅速判定）：中間順走査を用い、前の出力値と比較しながらトラバースする方法がおすすめです。

def is_bst_inorder(root):
    prev = None
    def inorder(node):
        nonlocal prev
        if not node:
            return True
        if not inorder(node.left):
            return False
        if prev is not None and node.val <= prev:
            return False
        prev = node.val
        return inorder(node.right)
    return inorder(root)

FAQ