Do inorder Traversal of BST and count number of elements traversed till now . As inorder traversal gives us the element in sorted Order, when count reaches k , we break out and Print the element.
/** * Definition for Binary Search Tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * }; */ int kthsmallest(TreeNode* root, int k) { if(root==NULL) return 0; stack<TreeNode*> s; bool complete=false; TreeNode* cur=root; int count=0; int val=0; while(!complete) { if(cur!=NULL) { s.push(cur); cur=cur->left; } else { if(!s.empty()) { count++; cur=s.top(); s.pop(); if(count==k) { val=cur->val; break; } cur=cur->right; } else complete=true; } } return val; }
Please comment if you find anything incorrect.