C++-এ বাইনারি ট্রির সর্ববৃহৎ সাবট্রি সম বের করুন

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

উদাহরণ

ট্রি: (রুট ৫, লেফ্ট -৪, রাইট ৪, -৪-র চাইল্ড ৩,৮; ৪-র চাইল্ড -৫,২)

• লেফ্ট সাবট্রি সম: ৩+৮+(-৪) = ৭
• রাইট সাবট্রি সম: -৫+২+৪ = ১
• পুরো ট্রি সম: ৫+৭+১ = ১৩

আউটপুট: 13

অ্যালগরিদম: পোস্ট-অর্ডার ট্রাভার্সাল

1. পোস্ট-অর্ডার (লেফ্ট → রাইট → রুট) ট্রাভার্সাল করুন।
2. প্রতিটি নোডের জন্য: currSum = node->data + leftSum + rightSum।
3. গ্লোবাল ans = max(ans, currSum) আপডেট করুন।
4. currSum রিটার্ন করুন প্যারেন্টের জন্য।

C++ প্রোগ্রাম

#include <iostream>
#include <algorithm>
using namespace std;

struct Node {
    int key;
    Node *left, *right;
};

Node* newNode(int key) {
    Node* temp = new Node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return temp;
}

int calcSumTreeSumRec(Node* root, int& ans) {
    if (root == NULL) return 0;
    int currSum = root->key + calcSumTreeSumRec(root->left, ans) + calcSumTreeSumRec(root->right, ans);
    ans = max(ans, currSum);
    return currSum;
}

int calcMaxSubTreeSum(Node* root) {
    if (root == NULL) return 0;
    int ans = INT_MIN;
    calcSumTreeSumRec(root, ans);
    return ans;
}

int main() {
    Node* root = newNode(5);
    root->left = newNode(-4);
    root->right = newNode(4);
    root->left->left = newNode(3);
    root->left->right = newNode(8);
    root->right->left = newNode(-5);
    root->right->right = newNode(2);
    cout << "The largest subtree sum is " << calcMaxSubTreeSum(root);
    return 0;
}

আউটপুট

The largest subtree sum is 13

ব্যাখ্যা

• পোস্ট-অর্ডার নিশ্চিত করে চাইল্ডদের সম আগে ক্যালকুলেট হয়।
• ans রেফারেন্স দিয়ে পাস করা হয়েছে যাতে সব রিকার্শন শেয়ার করে।
• নেগেটিভ ভ্যালু থাকলে INT_MIN ইনিশিয়ালাইজেশন জরুরি।
• টাইম: O(n), স্পেস: O(h) (রিকার্শন স্ট্যাক)।

বैरিয়েন্ট: সাবট্রি রুটও রিটার্ন করুন

যদি সাবট্রির রুট নোডও জানতে চান, তবে pair রিটার্ন করুন।