C++で平衡二分探索木から目標合計となるペアを見つける方法

平衡二分探索木（Balanced BST）と目標値（target sum）が与えられたとき、合計が目標値と等しくなるペアが木の中に存在するかどうかを判定するメソッドを実装することを考えます。この際、二分探索木は不変（immutable）である、つまり木の構造を変更してはいけないという制約があることに注意が必要です。

例えば、入力が以下のような木だったとします。

この場合、出力は (9 + 26 = 35) となります。

解決アプローチ

この問題は、ソート済み配列でよく使われる「二ポインタ（Two Pointers）」手法を、二分探索木に応用することで解けます。具体的には、以下の2つの走査を同時に進めていきます。

• 順方向の中順走査（In-order Traversal）：最小値から昇順に要素を取り出す
• 逆方向の中順走査（Reverse In-order Traversal）：最大値から降順に要素を取り出す

それぞれの走査にはスタックを1つずつ使用し、取り出した2つの値の合計を目標値と比較しながら、小さすぎれば昇順側を、大きすぎれば降順側を進めることで効率的にペアを探索します。

アルゴリズムの手順

• スタック s1、s2 を定義する
• done1 := false、done2 := false
• val1 := 0、val2 := 0
• curr1 := root、curr2 := root
• 無限ループを実行する：
  • done1 が false の間：
    • curr1 が NULL でなければ、curr1 を s1 にプッシュし、curr1 を左の子へ移動する
    • そうでなければ、s1 が空なら done1 := true。空でなければ、s1 の先頭要素を取り出して val1 にその値を格納し、curr1 を右の子へ移動して done1 := true とする
  • done2 が false の間：
    • curr2 が NULL でなければ、curr2 を s2 にプッシュし、curr2 を右の子へ移動する
    • そうでなければ、s2 が空なら done2 := true。空でなければ、s2 の先頭要素を取り出して val2 にその値を格納し、curr2 を左の子へ移動して done2 := true とする
  • val1 ≠ val2 かつ (val1 + val2) == target なら、ペアを出力して true を返す
  • (val1 + val2) < target なら、done1 := false として昇順側を次へ進める
  • (val1 + val2) > target なら、done2 := false として降順側を次へ進める
  • val1 >= val2 となった場合は、これ以上ペアが存在しないため false を返す

実装例

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

#include <bits/stdc++.h>
using namespace std;
#define MAX_SIZE 100
class TreeNode {
   public:
      int val;
      TreeNode *left, *right;
      TreeNode(int data) {
         val = data;
         left = NULL;
         right = NULL;
    }
};
bool isPairPresent(TreeNode* root, int target) {
   stack<TreeNode*> s1, s2;
   bool done1 = false, done2 = false;
   int val1 = 0, val2 = 0;
   TreeNode *curr1 = root, *curr2 = root;
   while (true) {
      while (done1 == false) {
         if (curr1 != NULL) {
            s1.push(curr1);
            curr1 = curr1->left;
         }
         else {
            if (s1.empty())
               done1 = 1;
            else {
               curr1 = s1.top();
               s1.pop();
               val1 = curr1->val;
               curr1 = curr1->right;
               done1 = 1;
            }
         }
      }
      while (done2 == false) {
         if (curr2 != NULL) {
            s2.push(curr2);
            curr2 = curr2->right;
         }
         else {
            if (s2.empty())
               done2 = 1;
            else {
               curr2 = s2.top();
               s2.pop();
               val2 = curr2->val;
               curr2 = curr2->left;
               done2 = 1;
            }
         }
      }
      if ((val1 != val2) && (val1 + val2) == target) {
         cout << "Pair Found: " << val1 << " + " << val2 << " = " << target << endl;
         return true;
      }
      else if ((val1 + val2) < target)
         done1 = false;
      else if ((val1 + val2) > target)
         done2 = false;
      if (val1 >= val2)
         return false;
   }
}
int main() {
   TreeNode* root = new TreeNode(16);
   root->left = new TreeNode(11);
   root->right = new TreeNode(21);
   root->left->left = new TreeNode(9);
   root->left->right = new TreeNode(13);
   root->right->left = new TreeNode(17);
   root->right->right = new TreeNode(26);
   int target = 35;
   cout << (isPairPresent(root, target));
}

入力

TreeNode* root = new TreeNode(16);
root->left = new TreeNode(11);
root->right = new TreeNode(21);
root->left->left = new TreeNode(9);
root->left->right = new TreeNode(13);
root->right->left = new TreeNode(17);
root->right->right = new TreeNode(26);

出力

Pair Found: 9 + 26 = 35
1

計算量の分析

このアルゴリズムでは、各ノードは高々1回ずつ訪問されるため、時間計算量は O(n) となります。また、使用するスタックの深さは木の高さに依存するため、平衡二分探索木の場合、空間計算量は O(log n) で抑えられます。木の構造を一切変更せずに済むため、不変なBSTが与えられた場合にも安全に適用できるのが大きな特徴です。