C++-এ বাইনারি ট্রি-এ পেরেন্ট-চাইল্ড সমের সর্বোচ্চ মান বের করার প্রোগ্রাম

সমস্যা বিবরণ

একটি বাইনারি ট্রি দেওয়া থাকলে, প্রতিটি পেরেন্ট নোড এবং এর দুটি চাইল্ড (যদি দুটোই থাকে) এর সম বের করুন এবং সর্বোচ্চ সম প্রিন্ট করুন।

সমাধানের পদ্ধতি (Recursive)

1. রিকার্সিভ ফাংশন maxSum(node) লিখুন।
2. বেস কেস: NULL → 0।
3. লেফ্ট সাবট্রির সর্বোচ্চ সম বের করুন।
4. যদি নোডের দুটি চাইল্ড থাকে:
   • sum = node->data + left->data + right->data
   • res = max(res, sum)
5. max(res, maxSum(right)) রিটার্ন করুন।

C++ কোড উদাহরণ

#include <iostream>
using namespace std;

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

Node* newNode(int n) {
    Node* root = new Node();
    root->data = n;
    root->left = root->right = NULL;
    return root;
}

int maxSum(Node* root) {
    if (root == NULL) return 0;
    int res = maxSum(root->left);
    if (root->left != NULL && root->right != NULL) {
        int sum = root->data + root->left->data + root->right->data;
        res = max(res, sum);
    }
    return max(res, maxSum(root->right));
}

int main() {
    Node* root = newNode(15);
    root->left = newNode(16);
    root->left->left = newNode(8);
    root->left->left->left = newNode(55);
    root->left->right = newNode(67);
    root->left->right->left = newNode(44);
    root->right = newNode(17);
    root->right->left = newNode(7);
    root->right->left->right = newNode(11);
    root->right->right = newNode(41);
    cout << maxSum(root);
    return 0;
}

আউটপুট

91

ব্যাখ্যা

পেরেন্ট-চাইল্ড জোড়া যেগুলোর দুটি চাইল্ড আছে: 16: 16+8+67=91 (সর্বোচ্চ) 67: 67+44=111? Wait, 67 has only left child. So not counted. 7: only right child. 15: 15+16+17=48 সর্বোচ্চ: 91

জটিলতা

• সময়: O(n)
• স্থান: O(h)