C++で二分木の中の最大BST（二分探索木）を見つける方法

二分木では、各子ノードが持てる子は最大2つ（左と右）です。木構造はデータを階層的に表現するシンプルな仕組みであり、その中でも二分探索木（BST：Binary Search Tree）は、次の条件を満たす特殊な二分木として定義されます。

• 左の子ノードは、親ノードより小さい値を持つ
• 右の子ノードは、親ノードより大きい値を持つ

本記事では、「与えられた二分木の中に含まれる最大のBST（部分木）を見つけ、そのサイズを返す」関数をC++で実装する方法を解説します。二分木そのものがBSTになっている場合は、二分木全体のサイズがそのまま答えになります。

問題の例

例1

入力：

      10
      /\
    5    15
   / \   \
  1   8    7

この場合、BSTとなっている部分木のうち最大のものはサイズ「3」です。したがって、戻り値は3となります。

例2

入力：

        52
       /  \
     37    67
    /  \  /  \
  12   27 57   77
              /\
            72  87

出力：

5

この例では、BSTを構成できる最大の部分木のノード数は5です。

最大のBSTを見つけるための考え方

あるノード x を根とする二分木がBSTであるためには、次の条件がすべて成立している必要があります。

• 左部分木には、親ノードより小さいデータを持つノードのみが存在する
• 右部分木には、親ノードより大きいデータを持つノードのみが存在する
• 左右どちらの部分木も、それぞれBSTである

アルゴリズム

二分木の根から処理を開始し、再帰を用いて各ノードを走査します。現在のノード「ROOT」に対しては、以下の手順を実行します。

• 現在のノードを根とする部分木が有効なBSTであれば、そのサイズを返す
• BSTでなければ、左部分木と右部分木それぞれの中で最大のBSTを探し、大きい方を返す

この方法では、各ノードごとにBST判定とサイズ計算を行うため、最悪の場合の時間計算量はO(n²)になります。ボトムアップ方式で情報を集約すればO(n)に改善できますが、まずは理解しやすい再帰によるシンプルな実装を見てみましょう。

C++での実装例

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    struct Node *left;
    struct Node *right;
};

struct Node *newNode(int data) {
    struct Node *node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return (node);
}

struct Detail {
    int size;
    int max;
    int min;
    int ans;
    bool isBST;
};

bool isBST(Node *root, int min, int max) {
    if (root == NULL) {
        return true;
    }
    if (root->data < min || root->data > max) {
        return false;
    }
    return isBST(root->left, min, root->data - 1) &&
           isBST(root->right, root->data + 1, max);
}

int size(Node *root) {
    if (root == NULL) {
        return 0;
    }
    return 1 + size(root->left) + size(root->right);
}

int largestBST(Node *root) {
    // 現在の部分木がBSTかどうかを判定
    if (isBST(root, INT_MIN, INT_MAX) == true) {
        return size(root);
    }
    // BSTでなければ、左右の部分木から最大のBSTを探す
    return max(largestBST(root->left), largestBST(root->right));
}

int main() {
    struct Node *root = newNode(67);
    root->left = newNode(72);
    root->right = newNode(77);
    root->left->left = newNode(57);
    printf("Size of the largest BST is %d", largestBST(root));
    return 0;
}

実行結果

Size of the largest BST is 2

まとめ

この記事では、二分木と二分探索木（BST）の基本概念を確認し、再帰を活用して与えられた二分木の中から最大のBSTを見つける方法を学びました。各ノードについて「その部分木がBSTかどうか」を再帰的に判定し、BSTであればサイズを、そうでなければ左右の部分木の結果の最大値を返すことで、目的の答えを得られます。シンプルで理解しやすい手法ですが、ノード数が多い場合は計算量に注意し、必要に応じてO(n)のボトムアップ方式への最適化も検討するとよいでしょう。