C++ में BST के प्रत्येक नोड में सभी बड़े मान जोड़ें

समस्या विवरण

एक बाइनरी सर्च ट्री (BST) दी गई है, प्रत्येक नोड को उसके मान और उससे बड़े सभी नोड्स के मानों के योग में बदलें।

हल दृष्टिकोण

रिवर्स इनऑर्डर ट्रैवर्सल (दाएं → नोड → बाएं) का उपयोग करें और एक चर में अब तक देखे गए नोड्स का योग बनाए रखें। प्रत्येक नोड के लिए, उसका मान वर्तमान योग में जोड़ें, फिर नोड का मान इस नए योग से बदलें।

उदाहरण कोड

#include <iostream>
using namespace std;

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

node* newNode(int key) {
    node* temp = new node;
    temp->left = 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() {
    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
73 72 67 60 50 35 25