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

এই সমস্যাতে, আমাদের একটি বাইনারি ট্রি দেওয়া আছে যেখানে প্রতিটি নোডের একটি মান রয়েছে। আমাদের কাজ হল ডাইনামিক প্রোগ্রামিং ব্যবহার করে বাইনারি ট্রিতে পরস্পর সংলগ্ন নয় এমন নোডগুলোর সর্বোচ্চ যোগফল খুঁজে বের করার প্রোগ্রাম তৈরি করা।

বাইনারি ট্রির সাবসেট নির্বাচন করব যেন যোগফল সর্বোচ্চ হয় এবং নোডগুলো সরাসরি সংযুক্ত নয়।

24

বিবেচনা করা উপাদানগুলো: 8 + 5 + 9 + 2 = 24

একটি সমাধান হল ম্যাপ ব্যবহার করে নোডগুলোর যোগফল খুঁজে বের করা যেন সেগুলো সর্বোচ্চ যোগফল তৈরি করে। শর্ত অনুযায়ী, পিতামাতা নোড এবং তার চাইল্ড নোড দুটি একসাথে বিবেচনা করা যাবে না। তাই, একটি নোড বিবেচনা করার আগে চেক করতে হবে তার চাইল্ড সাবট্রিতে কি কোথাও বড় যোগফল গঠনকারী উপাদান রয়েছে কিনা।

প্রতিটি নোডের জন্য একই পিতামাতা-চাইল্ড সাবট্রির যোগফল বারবার বের করলে কম্পিউটেশন ওভারহেড বাড়ে। এটিকে সমাধান করার জন্য আমরা মেমোরাইজেশন ব্যবহার করব এবং প্রতিটি নোড পর্যন্ত সর্বোচ্চ যোগফল একটি ম্যাপে সংরক্ষণ করব যেটি পরবর্তীতে ব্যবহার করা যাবে।

#include 
using namespace std;

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

struct node* newNode(int data) {
    struct node *temp = new struct node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}

int findMaxSumBT(node* node, map& nodeSum);

int sumSubTreeNodes(node* node, map& nodeSum) {
    int maxSum = 0;
    if (node->left)
        maxSum += findMaxSumBT(node->left->left, nodeSum) +
                  findMaxSumBT(node->left->right, nodeSum);
    if (node->right)
        maxSum += findMaxSumBT(node->right->left, nodeSum) +
                  findMaxSumBT(node->right->right, nodeSum);
    return maxSum;
}

int findMaxSumBT(node* node, map& nodeSum) {
    if (node == NULL)
        return 0;
    if (nodeSum.find(node) != nodeSum.end())
        return nodeSum[node];
    
    int sumInclCurr = node->data + sumSubTreeNodes(node, nodeSum);
    int sumExclCurr = findMaxSumBT(node->left, nodeSum) +
                      findMaxSumBT(node->right, nodeSum);
    
    nodeSum[node] = max(sumInclCurr, sumExclCurr);
    return nodeSum[node];
}

int main() {
    node* root = newNode(9);
    root->left = newNode(4);
    root->right = newNode(7);
    root->left->left = newNode(8);
    root->left->right = newNode(5);
    root->right->left = newNode(2);
    map nodeSum;
    cout << "Maximum sum of nodes in Binary tree such that no two are adjacent using Dynamic Programming is " << findMaxSumBT(root, nodeSum);
    return 0;
}

Maximum sum of nodes in Binary tree such that no two are adjacent using Dynamic Programming is 24