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

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

एल्गोरिदम

bstUpdate(root, sum) -

Begin
    if root is null, then stop
    bstUpdate(right of root, sum)
    sum := sum + value of root
    update root value using sum
    bstUpdate(left of root, sum)
End

उदाहरण

#include<iostream>
using namespace std;
class Node {
    public:
        int data;
        Node *left, *right;
};
Node *getNode(int item) {
    Node *newNode = new Node();
    newNode->data = item;
    newNode->left = newNode->right = NULL;
    return newNode;
}
void updateBST(Node *root, int *sum) {
    if (root == NULL)
        return;
    updateBST(root->right, sum); // दाएं सबट्री को अपडेट करें
    *sum = *sum + root->data;
    root->data = *sum; // रूट डेटा अपडेट करें
    updateBST(root->left, sum); // बाएं सबट्री को अपडेट करें
}
void BSTUpdate(Node *root) {
    int sum = 0;
    updateBST(root, &sum);
}
void inorder(Node *root) {
    if (root != NULL) {
        inorder(root->left);
        cout<data<<" ";
        inorder(root->right);
    }
}
Node* insert(Node* node, int data) {
    if (node == NULL)
        return getNode(data);
    if (data <= node->data) // बाएं जाएं
        node->left = insert(node->left, data);
    else // दाएं जाएं
        node->right = insert(node->right, data);
    return node;
}
int main() {
    int data[] = {50, 30, 20, 40, 70, 60, 80};
    int n = sizeof(data)/sizeof(data[0]);
    Node *root = NULL;
    for(int i = 0; i < n; i++) {
        root = insert(root, data[i]);
    }
    BSTUpdate(root);
    inorder(root);
}

आउटपुट

350 330 300 260 210 150 80