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

একটি বাইনারি ট্রি দেওয়া আছে। শুধু রাইট চাইল্ড নোডগুলোকে বিবেচনা করে তাদের মধ্যে সর্বোচ্চ মান বের করতে হবে।

উদাহরণ

ট্রি: (রুট ৫, লেফ্ট ৩, রাইট ২, ৩-র রাইট ৮, ২-র রাইট ৯)

রাইট নোডগুলো: {2, 8, 9} → সর্বোচ্চ: 9

অ্যালগরিদম

1. ট্রি রিকার্সিভলি ট্রাভার্স করুন।
2. প্রতিটি নোডের জন্য: যদি রাইট চাইল্ড থাকে, তার মান maxRight-এর সাথে কমপেয়ার করুন।
3. লেফ্ট ও রাইট সাবট্রি থেকে ম্যাক্স রিটার্ন করুন।

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

#include <iostream>
using namespace std;

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

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

int findMaxRightNode(Node* root) {
    int maxRight = -100;
    if (root == NULL) return -1;
    if (root->right != NULL)
        maxRight = root->right->data;
    return max(findMaxRightNode(root->right),
               max(maxRight, findMaxRightNode(root->left)));
}

int main() {
    Node* root = newNode(5);
    root->left = newNode(3);
    root->right = newNode(2);
    root->left->left = newNode(1);
    root->left->right = newNode(8);
    root->right->left = newNode(6);
    root->right->right = newNode(9);
    cout << "The maximum among all right nodes in Binary Tree is " << findMaxRightNode(root);
    return 0;
}

আউটপুট

The maximum among all right nodes in Binary Tree is 9

ব্যাখ্যা

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

ইটারেটিভ ভার্সন (BFS)

int findMaxRightNodeIterative(Node* root) {
    if (!root) return INT_MIN;
    queue<Node*> q;
    q.push(root);
    int maxRight = INT_MIN;
    while (!q.empty()) {
        Node* curr = q.front(); q.pop();
        if (curr->right) {
            maxRight = max(maxRight, curr->right->data);
            q.push(curr->right);
        }
        if (curr->left) q.push(curr->left);
    }
    return maxRight;
}