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

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

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

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

इनपुट

    10
    /  \
   /    \
  5     20
 / \   / \
1   7   1  5

आउटपुट

      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<<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() {
   /* Let us create following 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;
}