বাইনারি সার্চ ট্রি (BST)-এ প্রতিটি নোডে সব বড় মানগুলো যোগ করা C++-এ

বাইনারি সার্চ ট্রি (BST) হল বাইনারি ট্রির একটি রূপ যেখানে সব বাম নোডগুলো রুটের চেয়ে ছোট এবং সব ডান নোডগুলো রুটের চেয়ে বড় হয়। এই সমস্যাটিতে আমরা একটি বাইনারি ট্রি নিব এবং প্রতিটি নোডে তার চেয়ে বড় সব নোডের মান যোগ করব। অর্থাৎ "BST-এ প্রতিটি নোডে সব বড় মান যোগ করা" সমস্যাটি সরলীকৃত হয়: একটি BST-এ প্রতিটি নোডের মানকে তার চেয়ে বড় সব নোডের মানের যোগফলের সাথে যোগ করা।

ব্যাখ্যা

এই প্রোগ্রামটি একটি 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() {
    /* নিচের 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;
}