Pythonで二分探索木（BST）の妥当性を検証する方法

二分木が与えられたとき、それが有効な二分探索木（BST：Binary Search Tree）であるかどうかを判定する問題を考えてみましょう。

二分探索木は、以下の条件を満たすものとして定義されます。

• あるノードの左部分木に含まれるノードのキーは、すべてそのノードのキーより小さい値であること。
• あるノードの右部分木に含まれるノードのキーは、すべてそのノードのキーより大きい値であること。
• 左部分木と右部分木も、それぞれ二分探索木でなければならないこと。

例えば、次のような二分木が与えられた場合を考えます。

この場合、出力は true となります。

解法のアプローチ

この問題を解くためには、以下の手順に従います。

• solve() という再帰関数を作成します。この関数は root（現在のノード）、min（許容される最小値）、max（許容される最大値） の3つの引数を受け取ります。
• root が null（空）の場合は true を返します。空の木は有効なBSTとみなせるためです。
• root の値が min 以下、または max 以上の場合は false を返します。これはBSTの条件に違反していることを意味します。
• それ以外の場合は、solve(左の子, min, rootの値) と solve(右の子, rootの値, max) の結果の論理積（AND）を返します。
• 最初に solve() を呼び出す際には、min として負の無限大（-inf）、max として正の無限大（inf）を渡します。

この方法のポイントは、各ノードに対して「取りうる値の範囲」を伝播させていくことです。左に降りるときは上限が現在のノードの値に更新され、右に降りるときは下限が更新されます。これにより、単に親子関係だけを見るのではなく、祖先全体との整合性を正しくチェックできます。

Pythonでの実装例

以下のコードで、実際の実装を確認してみましょう。

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

def insert(temp,data):
    que = []
    que.append(temp)
    while (len(que)):
        temp = que[0]
        que.pop(0)
        if (not temp.left):
            if data is not None:
                temp.left = TreeNode(data)
            else:
                temp.left = TreeNode(0)
            break
        else:
            que.append(temp.left)
        if (not temp.right):
            if data is not None:
                temp.right = TreeNode(data)
            else:
                temp.right = TreeNode(0)
            break
        else:
            que.append(temp.right)

def make_tree(elements):
    Tree = TreeNode(elements[0])
    for element in elements[1:]:
        insert(Tree, element)
    return Tree

class Solution(object):
    def isValidBST(self, root):
        return self.solve(root,-1000000000000000000000,1000000000000000000000)
    
    def solve(self,root,min_val,max_val):
        if root == None or root.data == 0:
            return True
        if (root.data <= min_val or root.data >=max_val):
            return False
        return self.solve(root.left,min_val,root.data) and self.solve(root.right,root.data,max_val)

ob1 = Solution()
tree = make_tree([3,1,4,None,2,None,5])
print(ob1.isValidBST(tree))
tree = make_tree([5,1,4,None,None,3,6])
print(ob1.isValidBST(tree))

入力

[3,1,4,null,2,null,5]
[5,1,4,null,null,3,6]

出力

true
false

コードの解説

最初の入力 [3,1,4,null,2,null,5] では、ルートが3、左の子が1、右の子が4となっており、さらに4の左に2、右に5が配置されています。すべてのノードがBSTの条件（左の子 < 親 < 右の子、および祖先との範囲制約）を満たしているため、結果は true です。

一方、2番目の入力 [5,1,4,null,null,3,6] では、ルート5の右部分木に4が含まれています。右部分木のすべてのノードはルートより大きい必要があるため、これはBSTの定義に違反し、結果は false となります。

計算量について

このアルゴリズムの時間計算量は O(n)（nはノード数）です。各ノードを一度だけ訪問するためです。空間計算量は再帰呼び出しのスタック深さに依存し、最悪の場合（木が偏っている場合）は O(n)、バランスの取れた木の場合は O(log n) となります。