C++-এ BST-তে K-তম ক্ষুদ্রতম উপাদান খুঁজে বের করা (Order Statistics)

বাইনারি সার্চ ট্রি (BST) এবং একটি মান K দেওয়া আছে। ট্রিতে K-তম ক্ষুদ্রতম উপাদান খুঁজে বের করতে হবে।

ইনপুট উদাহরণ:

k = 3 হলে আউটপুট ১৫।

সমাধানের ধাপসমূহ

find_kth_smallest() ফাংশন ডিফাইন করুন যা root, count, K নেয়।
যদি root NULL হয় তবে NULL ফেরত দিন।
বাম সাবট্রি থেকে খুঁজুন। পাওয়া গেলে ফেরত দিন।
count বেড়ান। যদি count == K হয় তবে root ফেরত দিন।
ডান সাবট্রি থেকে খুঁজুন।
মেইন মেথডে count=0 দিয়ে কল করুন এবং ফলাফল প্রিন্ট করুন।

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

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) { val = x; left = right = NULL; }
};

TreeNode* find_kth_smallest(TreeNode* root, int &count, int k) {
    if (root == NULL) return NULL;
    TreeNode* left = find_kth_smallest(root->left, count, k);
    if (left != NULL) return left;
    count++;
    if (count == k) return root;
    return find_kth_smallest(root->right, count, k);
}

void kth_smallest(TreeNode* root, int k) {
    int count = 0;
    TreeNode* res = find_kth_smallest(root, count, k);
    if (res == NULL) cout << "Not found";
    else cout << res->val;
}

int main() {
    TreeNode* root = new TreeNode(25);
    root->left = new TreeNode(13);
    root->right = new TreeNode(27);
    root->left->left = new TreeNode(9);
    root->left->right = new TreeNode(17);
    root->left->right->left = new TreeNode(15);
    root->left->right->right = new TreeNode(19);
    int k = 3;
    kth_smallest(root, k);
}

ইনপুট

TreeNode* root = new TreeNode(25); ... k = 3