Pythonで二分木が二分探索木（BST）かどうかを判定する方法

はじめに：BSTとは何か

二分木が与えられたとき、それが二分探索木（Binary Search Tree：BST）であるかどうかを判定することは、データ構造の学習やコーディング面接でよく出題される定番の問題です。

BSTには以下のような重要な性質があります。

• 左部分木に含まれるすべてのノードの値は、現在のノードの値より小さい
• 右部分木に含まれるすべてのノードの値は、現在のノードの値より大きい
• これらの性質は、木の中のすべてのノードに対して再帰的に成り立つ

たとえば、次のような二分木を考えてみましょう。

• ルート：5
• 左の子：1
• 右の子：9（その左の子：7、さらに左の子：6・右の子：8／右の子：10）

この場合、すべてのノードがBSTの条件を満たしているため、出力は True になります。

解決のアプローチ

この問題を解く最もシンプルで直感的な方法は、中間順走査（Inorder Traversal）を利用することです。BSTを中間順で走査すると、必ず昇順にソートされた値の列が得られるという性質があります。この性質を利用して、次の手順で判定します。

1. 木の要素を中間順走査し、結果をリスト x に格納する
2. x が昇順にソートされていれば True を返す
3. そうでなければ False を返す

実装例

以下がPythonでの具体的な実装です。

class TreeNode:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

class Solution:
    def solve(self, root):
        def inorder(root, l):
            if root is None:
                return
            inorder(root.left, l)
            l.append(root.data)
            inorder(root.right, l)

        l = []
        inorder(root, l)
        return l == sorted(l)

ob = Solution()
root = TreeNode(5)
root.left = TreeNode(1)
root.right = TreeNode(9)
root.right.left = TreeNode(7)
root.right.right = TreeNode(10)
root.right.left.left = TreeNode(6)
root.right.left.right = TreeNode(8)
print(ob.solve(root))

入力

root = TreeNode(5)
root.left = TreeNode(1)
root.right = TreeNode(9)
root.right.left = TreeNode(7)
root.right.right = TreeNode(10)
root.right.left.left = TreeNode(6)
root.right.left.right = TreeNode(8)

出力

True

コードの解説

このコードの動作を簡単に整理してみましょう。

• TreeNode クラスは、各ノードが保持する値（data）、左の子（left）、右の子（right）を表現します。
• solve メソッド内で定義された inorder 関数は、再帰的に木を中間順（左 → 自身 → 右）で走査し、訪問したノードの値をリスト l に追加していきます。
• 最後に l == sorted(l) を評価することで、走査結果が昇順に並んでいるかどうかを確認します。並んでいればBSTであると判定できます。

計算量について

この手法の時間計算量は O(n)（中間順走査）＋ O(n log n)（ソートと比較）となり、全体としては O(n log n) です。また、補助リスト用に O(n) のメモリが必要になります。なお、各ノードの値の範囲（最小値・最大値）を引数として渡しながら再帰的に検証する方法を使えば、O(n) の時間計算量で判定することも可能です。

まとめ

「中間順走査の結果がソート済みならBST」という性質を利用すれば、わずか数行のコードで二分木がBSTかどうかを簡潔に判定できます。アルゴリズムの理解を深めるためにも、ぜひ自分でもコードを書いて試してみてください。