http://www.geeksforgeeks.org/find-k-th-smallest-element-in-bst-order-statistics-in-bst/
1 #include <iostream> 2 #include <vector> 3 #include <algorithm> 4 #include <queue> 5 #include <stack> 6 #include <string> 7 #include <fstream> 8 #include <map> 9 using namespace std; 10 11 struct node { 12 int data; 13 struct node *left, *right; 14 node() : data(0), left(NULL), right(NULL) { } 15 node(int d) : data(d), left(NULL), right(NULL) { } 16 }; 17 18 node *insert(node *root, int key) { 19 if (!root) return new node(key); 20 if (root->data > key) root->left = insert(root->left, key); 21 else root->right = insert(root->right, key); 22 return root; 23 } 24 25 void prints(node *root) { 26 if (!root) return; 27 prints(root->left); 28 cout << root->data << " "; 29 prints(root->right); 30 } 31 32 node *k_smallest(node *root, int k) { 33 stack<node*> S; 34 while (1) { 35 while (root) { 36 S.push(root); 37 root = root->left; 38 } 39 if (!S.empty()) { 40 root = S.top(); 41 S.pop(); 42 if (k-1 == 0) return root; 43 k--; 44 root = root->right; 45 } 46 else break; 47 } 48 return NULL; 49 } 50 51 int main() { 52 node *root = NULL; 53 root = insert(root, 50); 54 insert(root, 30); 55 insert(root, 20); 56 insert(root, 40); 57 insert(root, 70); 58 insert(root, 60); 59 insert(root, 80); 60 if (k_smallest(root, 5)) cout << k_smallest(root, 5)->data << endl; 61 else cout << "No node" << endl; 62 return 0; 63 }