मान लीजिए कि हमारे पास एक बाइनरी सर्च ट्री है और इनपुट के रूप में एक मान K है, तो हमें ट्री में K-वें सबसे छोटा तत्व खोजना होगा।
तो, अगर इनपुट पसंद है
k =3, तो आउटपुट 15 होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
फ़ंक्शन को परिभाषित करें find_kth_smallest(), यह रूट लेगा, काउंट, k,
-
यदि रूट NULL है, तो -
-
वापसी शून्य
-
-
बायाँ =find_kth_smallest (रूट के बाएँ, गिनती, k)
-
यदि बायाँ NULL नहीं है, तो -
-
बाएं लौटें
-
-
(1 से गिनती बढ़ाएं)
-
यदि गिनती k के समान है, तो -
-
वापसी जड़
-
-
वापसी find_kth_smallest (रूट के दाईं ओर, गिनती, k)
-
मुख्य विधि से, निम्न कार्य करें -
-
गिनती :=0
-
res =find_kth_smallest (रूट, काउंट, k)
-
अगर रेस न्यूल है, तो -
-
प्रदर्शन नहीं मिला
-
-
अन्यथा
-
रेस का प्रदर्शन वैल
-
उदाहरण (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
