C++-এ বাইনারি ট্রির প্রতিটি লেভেলের লীফ নোডগুলোর যোগফলের গুণফল বের করা

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

উদাহরণ ১

    3
   / \
  8   6
       \
       10

আউটপুট: 80 (লেভেল ২: ৮, লেভেল ৩: ১০ → ৮×১০=৮০)

উদাহরণ ২

      3
     / \
    8   6
   / \   \
  9  7   10
 / \  / \
2 12 5 11

আউটপুট: 270 (লেভেল ৩: ৯, লেভেল ৪: ২+১২+৫+১১=৩০ → ৯×৩০=২৭০)

অ্যালগরিদম (লেভেল অর্ডার ট্রাভার্সাল + কিউ)

• কিউ দিয়ে লেভেল অর্ডার ট্রাভার্সাল করুন।
• প্রতিটি লেভেলে লীফ নোড পাওয়া যাবে কিনা চেক করুন।
• লীফ পাওয়া গেলে সে লেভেলের লীফগুলোর যোগফল নিয়ে মাল্টিপ্লাই করুন।

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

#include <bits/stdc++.h>
using namespace std;

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

bool isLeaf(Node* root) { return !root->left && !root->right; }

int sumAndMultiplyLevelData(Node* root) {
    if (!root) return 0;
    int mul = 1;
    queue<Node*> q;
    q.push(root);

    while (true) {
        int nodeCount = q.size();
        if (nodeCount == 0) break;
        int levelSum = 0;
        bool leafFound = false;
        while (nodeCount--) {
            Node* nd = q.front(); q.pop();
            if (isLeaf(nd)) {
                leafFound = true;
                levelSum += nd->data;
            }
            if (nd->left) q.push(nd->left);
            if (nd->right) q.push(nd->right);
        }
        if (leafFound) mul *= levelSum;
    }
    return mul;
}

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

int main() {
    Node* root = newNode(3);
    root->left = newNode(8); root->right = newNode(6);
    root->left->right = newNode(7);
    root->left->left = newNode(9);
    root->left->right->left = newNode(2);
    root->left->right->right = newNode(12);
    root->right->right = newNode(10);
    root->right->right->left = newNode(5);
    root->right->right->right = newNode(11);
    cout << "Final product value = " << sumAndMultiplyLevelData(root) << endl;
    return 0;
}

আউটপুট: Final product value = 270