JavaScriptで2つの二分探索木（BST）のノード値の合計が目標値に一致するか判定する方法

問題

JavaScriptの関数を作成します。この関数は、第1引数として1つ目の二分探索木のルートroot1を、第2引数として2つ目の二分探索木のルートroot2を受け取り、さらに第3引数として整数targetを受け取ります。

この関数は、「1つ目の木の中のあるノード」と「2つ目の木の中のあるノード」の値を足し合わせた結果がtargetと一致するようなペアが存在する場合にのみtrueを返し、存在しない場合はfalseを返す必要があります。

たとえば、次のような入力が与えられたとします。

const target = 23;

2つのBSTの例

この場合の出力は次のようになります。

const output = true;

出力の説明

1つ目の木には「6」、2つ目の木には「17」が存在し、6 + 17 = 23 となるため、出力はtrueになります。

実装例

まず、二分探索木のノードクラスと挿入処理を実装します。

class Node{
   constructor(data) {
      this.data = data;
      this.left = null;
      this.right = null;
   };
};
class BinarySearchTree{
   constructor(){
      // 二分探索木のルート
      this.root = null;
   }
   insert(data){
      var newNode = new Node(data);
      if(this.root === null){
         this.root = newNode;
      }else{
         this.insertNode(this.root, newNode);
      };
   };
   insertNode(node, newNode){
      if(newNode.data < node.data){
         if(node.left === null){
            node.left = newNode;
         }else{
            this.insertNode(node.left, newNode);
         };
      } else {
         if(node.right === null){
            node.right = newNode;
         }else{
            this.insertNode(node.right,newNode);
         };
      };
   };
};

続いて、2つの木を構築し、目的の判定を行う関数twoSumBSTsを実装します。

const tree1 = new BinarySearchTree();
tree1.insert(1);
tree1.insert(3);
tree1.insert(4);
tree1.insert(2);
tree1.insert(4);
tree1.insert(5);
tree1.insert(6);
const tree2 = new BinarySearchTree();
tree2.insert(9);
tree2.insert(6);
tree2.insert(11);
tree2.insert(3);
tree2.insert(8);
tree2.insert(10);
tree2.insert(17);
const twoSumBSTs = (root1, root2, target) => {
   if(root1 == null || root2 == null) return false;
   if(root1.data + root2.data == target) return true;
   if(root1.data + root2.data < target) {
      return twoSumBSTs(root1.right, root2, target) || twoSumBSTs(root1, root2.right, target);
   }else{
      return twoSumBSTs(root1.left, root2, target) || twoSumBSTs(root1,
      root2.left, target);
   };
};
const target = 23;
console.log(twoSumBSTs(tree1.root, tree2.root, target));

出力

コンソールには次のように表示されます。

true

アルゴリズムのポイント

この実装では、二分探索木（BST）の性質を活かした再帰的な探索を行っています。現在注目している2つのノードの値の合計がtargetより小さい場合、より大きい値を得るためにどちらかの木の右側部分木へ進みます。逆に合計がtargetより大きい場合は、より小さい値を求めて左側部分木へ進みます。

これにより、すべてのノードの組み合わせを総当たりで確認するよりも効率的に答えを求めることができます。どちらかのノードがnullになった時点でその経路には解が存在しないためfalseを返し、合計が一致した時点で即座にtrueを返して探索を終了します。