PythonのBST（二分探索木）に指定した合計になるトリプレットが存在するか判定する方法

問題概要

整数値を持つ二分探索木（BST）と、ある数値「total」が与えられたとします。このとき、BSTの中から3つの要素を選び、その合計が「total」と一致するような組み合わせ（トリプレット）が存在するかどうかを判定するのが、本記事のテーマです。

例えば、次のようなBSTが入力として与えられた場合を考えてみます。

total = 12 の場合、出力は True になります。

解法のアプローチ

この問題は、BSTを中順走査（inorder traversal）するとノードの値が昇順に並ぶという性質を利用することで、効率的に解くことができます。全体の流れは以下の通りです。

1. 結果を格納するための空のリスト temp_list を用意し、木を中順走査してすべてのノードの値を昇順に追加する
2. リストの先頭側から順に、要素 temp_list[i] を1つ目の値として固定する
3. 残りの範囲に対して、左端（left）と右端（right）の2つのポインタを使い、合計が total になるペアを探す

ポインタの動かし方は次の通りです。

• temp_list[i] + temp_list[left] + temp_list[right] が total と等しい場合 → True を返す
• 合計が total より小さい場合 → 合計を大きくするため、left を1つ右へ移動する
• 合計が total より大きい場合 → 合計を小さくするため、right を1つ左へ移動する

すべての候補を試しても条件を満たすトリプレットが見つからなければ、False を返します。

実装例

それでは、実際のPythonコードを見てみましょう。

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

def traverse_inorder(tree_root, inorder):
    if tree_root is None:
        return
    traverse_inorder(tree_root.left, inorder)
    inorder.append(tree_root.value)
    traverse_inorder(tree_root.right, inorder)

def solve(tree_root, total):
    temp_list = []
    traverse_inorder(tree_root, temp_list)
    n = len(temp_list)
    for i in range(n - 2):
        left = i + 1
        right = n - 1
        while left < right:
            current_sum = temp_list[i] + temp_list[left] + temp_list[right]
            if current_sum == total:
                return True
            elif current_sum < total:
                left += 1
            else:
                right -= 1
    return False

tree_root = TreeNode(5)
tree_root.left = TreeNode(3)
tree_root.right = TreeNode(7)
tree_root.left.left = TreeNode(2)
tree_root.left.right = TreeNode(4)
tree_root.right.left = TreeNode(6)
tree_root.right.right = TreeNode(8)

print(solve(tree_root, 12))

入力

tree_root = TreeNode(5)
tree_root.left = TreeNode(3)
tree_root.right = TreeNode(7)
tree_root.left.left = TreeNode(2)
tree_root.left.right = TreeNode(4)
tree_root.right.left = TreeNode(6)
tree_root.right.right = TreeNode(8)
total = 12

出力

True

計算量の評価

中順走査に O(n)、その後の二重ループによる探索に O(n²) の時間がかかるため、全体の時間計算量は O(n²) となります。また、走査結果を保持するリストが必要なため、空間計算量は O(n) です。全ノードの組み合わせを総当たりする O(n³) の素朴な手法と比べて大幅に効率化できる点が、このアルゴリズムの大きなポイントです。