C++でBST（二分探索木）の全ノードに、より大きい値の合計を加算する方法

BST（Binary Search Tree：二分探索木）とは、二分木の一種であり、根（ルート）の値より小さい値を持つノードがすべて左側に、大きい値を持つノードがすべて右側に配置されるデータ構造です。

本記事で扱う問題「BSTの各ノードに、より大きい値をすべて加算する」は、次のように要約できます。与えられたBSTに対して、現在のノードの値よりも大きいすべてのノードの値を合計し、その合計を該当ノードに加算するというものです。

問題の定義

二分探索木（BST）が与えられたとき、各ノードに対して、そのノードより大きい値を持つすべてのノードの値の総和を加算する必要があります。

例えば、次のようなBSTを考えます。

変換後の木では、各ノードの値は「元の値＋それより大きい要素の合計」となります。つまり、このプログラムはBSTを、各ノードの値がそれより大きい全要素の合計と元の値の和である二分木へと変換します。

解法のアプローチ

この問題を解く鍵となるのは逆中順走査（Reverse Inorder Traversal）です。通常の中順走査は「左部分木 → 根 → 右部分木」の順で訪問しますが、逆中順走査では右部分木から先に再帰呼び出しを行います。

これにより、ノードを降順に訪問できるため、以下の手順で処理します。

1. これまでに走査したノードの値の累積和を保持する変数 sum を用意します。
2. 右部分木を先に走査し、その後現在のノードの値を sum に加算します。
3. 現在のノードの値を更新後の sum で置き換えます。
4. 最後に左部分木を走査します。

こうすることで、各ノードには「自分自身を含む、自分以上の値の総和」が格納されます。

C++による実装例

#include <iostream>
using namespace std;

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

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

void Inorder(node *root) {
    if (!root)
        return;
    Inorder(root->left);
    cout << root->data << " ";
    Inorder(root->right);
}

node *Insert(node *root, int key) {
    if (!root)
        return newNode(key);
    if (key < root->data)
        root->left = Insert(root->left, key);
    else
        root->right = Insert(root->right, key);
    return root;
}

// 逆中順走査で累積和を適用
void RevInorderAdd(node *root, int &sum) {
    if (!root)
        return;
    RevInorderAdd(root->right, sum);  // 右部分木を先に処理
    sum += root->data;                // 現在の値を累積和に追加
    root->data = sum;                 // ノードの値を更新
    RevInorderAdd(root->left, sum);   // 左部分木を処理
}

void AddGreater(node *root) {
    int sum = 0;
    RevInorderAdd(root, sum);
}

int main() {
    /* 次のBSTを作成します
          10
         /  \
        5    20
       / \   / \
      1   7 15  25 */
    node *root = NULL;
    root = Insert(root, 10);
    Insert(root, 20);
    Insert(root, 25);
    Insert(root, 15);
    Insert(root, 5);
    Insert(root, 7);
    Insert(root, 1);

    // 変換前の木を出力（昇順表示）
    Inorder(root);
    cout << endl;

    // 各ノードにより大きい値を加算
    AddGreater(root);

    // 変換後の木を出力
    Inorder(root);
    cout << endl;

    return 0;
}

実行結果

1 5 7 10 15 20 25
88 83 78 71 61 46 25

動作の解説

上記のコードでは、まず値 1, 5, 7, 10, 15, 20, 25 を持つBSTを構築しています。逆中順走査により、最大値 25 から順に訪問し、累積和を計算していきます。

• 25 → 累積和は 25 のまま
• 20 → 20 + 25 = 45
• 15 → 15 + 45 = 60
• 10 → 10 + 60 = 70
• 7 → 7 + 70 = 77
• 5 → 5 + 77 = 82
• 1 → 1 + 82 = 83

このように、各ノードの値が「自分自身＋それより大きい全ノードの合計」に置き換えられます。

計算量

• 時間計算量： O(n) — 各ノードを一度だけ訪問します。
• 空間計算量： O(h) — 再帰の深さは木の高さ h に依存します（平衡な木なら O(log n)）。