ধরুন আমাদের কাছে একটি বাইনারি সার্চ ট্রি এবং ইনপুট হিসাবে একটি মান K আছে, আমাদের গাছের মধ্যে K-তম ক্ষুদ্রতম উপাদান খুঁজে বের করতে হবে।
সুতরাং, যদি ইনপুট মত হয়
k =3, তাহলে আউটপুট হবে 15।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি ফাংশন সংজ্ঞায়িত করুন find_kth_smallest(), এটি রুট, গণনা, কে,
নেবে -
রুট যদি NULL হয়, তাহলে -
-
রিটার্ন NULL
-
-
left =find_kth_smallest(মূলের বামে, গণনা, k)
-
বাম যদি NULL না হয়, তাহলে -
-
বাম দিকে ফিরুন
-
-
(গণনা 1 দ্বারা বৃদ্ধি করুন)
-
যদি গণনা k এর সমান হয়, তাহলে −
-
রিটার্ন রুট
-
-
ফিরুন find_kth_smallest(মূলের ডানদিকে, গণনা, কে)
-
প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -
-
গণনা :=0
-
res =find_kth_smallest(root, count, k)
-
res যদি NULL হয়, তাহলে -
-
ডিসপ্লে পাওয়া যায়নি
-
-
অন্যথায়
-
রেজুলেশনের ডিসপ্লে ভ্যাল
-
উদাহরণ (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); 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); k = 3
আউটপুট
15
