C++-এ বাইনারি ট্রি-এ ম্যাক্সিমাল ভ্যালু রুট (Maximal Value Roots) গণনা করার প্রোগ্রাম

সমস্যা বিবরণ

একটি বাইনারি ট্রি দেওয়া থাকলে, কতগুলো নোড আছে যাদের ভ্যালু তাদের সব ডিসেন্ডেন্ট (वंশজ) নোডগুলোর ভ্যালু থেকে বড় বা সমান তা গণনা করুন।

সমাধানের পদ্ধতি (Post-order DFS)

1. DFS ফাংশন লিখুন যা সাবট্রির সর্বোচ্চ ভ্যালু রিটার্ন করে।
2. বেস কেস: NULL → 0 (অথবা INT_MIN, কিন্তু কোডে 0)۔
3. লেফ্ট এবং রাইট সাবট্রির ম্যাক্স ভ্যালু বের করুন (l, r)।
4. যদি node->val >= max(l, r) হয়, তবে কাউন্ট বাড়ান।
5. max(node->val, l, r) রিটার্ন করুন।

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

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

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data) {
        val = data;
        left = right = NULL;
    }
};

class Solution {
public:
    int ret;
    int dfs(TreeNode* node) {
        if (!node) return 0;
        int l = dfs(node->left);
        int r = dfs(node->right);
        if (node->val >= max(l, r)) {
            ret++;
        }
        int x = max({node->val, l, r});
        return x;
    }
    int solve(TreeNode* root) {
        ret = 0;
        dfs(root);
        return ret;
    }
};

int main() {
    Solution ob;
    TreeNode* root = new TreeNode(7);
    root->left = new TreeNode(4);
    root->right = new TreeNode(3);
    root->right->left = new TreeNode(7);
    root->right->right = new TreeNode(5);
    cout << ob.solve(root);
    return 0;
}

আউটপুট

4

ব্যাখ্যা

ট্রি: 7(রুট) -> L:4, R:3 -> 3-এর চাইল্ড: 7, 5

নোড ৭ (রুট): ডিসেন্ডেন্ট ম্যাক্স = ৭ → ৭>=৭ ✓

নোড ৪: লিফ → ✓

নোড ৩: ডিসেন্ডেন্ট ম্যাক্স = ৭ → ৩>=৭ ✗

নোড ৭ (রাইট-লেফ্ট): লিফ → ✓

নোড ৫: লিফ → ✓

মোট ৪টি নোড।

জটিলতা

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