मान लीजिए हमारे पास एक बाइनरी सर्च ट्री और एक मान K इनपुट के रूप में है, हमें ट्री में K-वां सबसे छोटा तत्व ढूंढना है।
तो, यदि इनपुट इस तरह है

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