सी++ में बीएसटी (बीएसटी में ऑर्डर सांख्यिकी) में के-वें सबसे छोटे तत्व का पता लगाएं

मान लीजिए कि हमारे पास एक बाइनरी सर्च ट्री है और इनपुट के रूप में एक मान 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