C++-এ বাইনারি ট্রিতে সর্বোচ্চ ও ন্যূনতম মান বের করুন

একটি বাইনারি ট্রি দেওয়া আছে। ট্রির সব নোডের মধ্যে সর্বোচ্চ (max) এবং ন্যূনতম (min) মান বের করতে হবে।

উদাহরণ

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

আউটপুট: max = 9, min = 1

অ্যালগরিদম (রিকার্সিভ)

1. বেস কেস: root == NULL → INT_MIN (max) / INT_MAX (min) রিটার্ন।
2. বাম সাবট্রির ম্যাক্স/মিন, ডান সাবট্রির ম্যাক্স/মিন, এবং বর্তমান নোডের মান — এই তিনটির ম্যাক্স/মিন বের করুন।

C++ প্রোগ্রাম (সর্বোচ্চ মান)

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

class Node {
public:
    int data;
    Node *left, *right;
    Node(int data) {
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};

int findMaxNode(Node* root) {
    if (root == NULL) return INT_MIN;
    int maxVal = root->data;
    int leftMax = findMaxNode(root->left);
    int rightMax = findMaxNode(root->right);
    if (leftMax > maxVal) maxVal = leftMax;
    if (rightMax > maxVal) maxVal = rightMax;
    return maxVal;
}

int findMinNode(Node* root) {
    if (root == NULL) return INT_MAX;
    int minVal = root->data;
    int leftMin = findMinNode(root->left);
    int rightMin = findMinNode(root->right);
    if (leftMin < minVal) minVal = leftMin;
    if (rightMin < minVal) minVal = rightMin;
    return minVal;
}

int main() {
    Node* root = new Node(5);
    root->left = new Node(3);
    root->right = new Node(2);
    root->left->left = new Node(1);
    root->left->right = new Node(8);
    root->right->left = new Node(6);
    root->right->right = new Node(9);
    cout << "The Maximum element of Binary Tree is " << findMaxNode(root) << endl;
    cout << "The Minimum element of Binary Tree is " << findMinNode(root) << endl;
    return 0;
}

আউটপুট

The Maximum element of Binary Tree is 9
The Minimum element of Binary Tree is 1

ব্যাখ্যা

• রিকার্শন ট্রি-ট্রাভার্সালের সহজতম পদ্ধতি।
• INT_MIN/INT_MAX বেস কেস হিসেবে ব্যবহার করা হয়েছে যাতে যেকোনো পজিটিভ/নেগেটিভ মান হ্যান্ডেল হয়।
• টাইম: O(n) — সব নোড একবার ভিজিট হয়।
• স্পেস: O(h) — রিকার্শন স্ট্যাক (h = ট্রির হাইট)।

ইটারেটিভ (BFS) বিকল্প

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