दिए गए BST में प्रत्येक नोड में सभी बड़े मान जोड़ें?

BST या बाइनरी सर्च ट्री बाइनरी ट्री का एक रूप है जिसमें सभी बाएं नोड्स छोटे होते हैं और सभी दाएं नोड्स रूट मान से बड़े होते हैं। इस समस्या के लिए, हम एक बाइनरी ट्री लेंगे और वर्तमान नोड से बड़े सभी मानों को इसमें जोड़ेंगे। समस्या "BST में प्रत्येक नोड में सभी बड़े मान जोड़ें" को सरल रूप में इस प्रकार कहा जा सकता है: एक BST के लिए, उस नोड मान से बड़े सभी नोड मानों को उस नोड मान में जोड़ें।

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

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

इनपुट

    10
   /  \
  /    \
 5      20
/ \    / \
1  7  15 25

आउटपुट

     70
   /  \
  82   45
 / \  / \
83 77 60 25

व्याख्या

यह प्रोग्राम एक BST को एक बाइनरी ट्री में बदल देगा जहां नोड्स के मान सभी बड़े एलिमेंट्स के योग और नोड के मूल मान के योग के बराबर होंगे।

बाइनरी सर्च ट्री में प्रत्येक नोड में सभी बड़े मान जोड़ने का समाधान:

हम रिवर्स इनऑर्डर ट्रैवर्सल (पहले दाएं सबट्री पर पुनरावृत्ति कॉल की जाती है बजाय बाएं सबट्री के) का उपयोग करते हैं और एक वेरिएबल बनाए रखते हैं जो अब तक पार किए गए नोड्स के योग को स्टोर करता है।

फिर हम इस योग का उपयोग अपने वर्तमान नोड के मान को संशोधित करने के लिए करते हैं, पहले इसके मान को योग में जोड़कर, और फिर नोड के मान को इस योग से बदलकर।

उदाहरण

#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<data<<" ";
    Inorder(root->right);
}
node *Insert(node *root,int key) {
    if(!root)
        return newNode(key);
    if(keydata)
        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<