# C++ code with explanation and annotation, using nonrecursive inorder traversal

• To solve this problem, you need to know the definition of BST (binary search tree), here is the wiki link: https://en.wikipedia.org/wiki/Binary_search_tree
According to the definition of BST, the key in each node must be greater than all keys stored in the left sub-tree, and smaller than all keys in the right sub-tree.
If you know that the inorder traversal of a BST tree is an ascending order sequence (you should verify this by yourself), then we only need to output the k-th elements in the inorder traversal sequence.
Here is my code, a implementation of nonrecursive inorder traversal, you can very easily to implement the nonrecursive preorder and postorder traversal based on this code.

``````class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
if( root == NULL ){   // null, return a special value
return 0;
}
int count = 0;  // how many elements we have record, if count==k, then stop
int min = root->val; // for the case when k is larger than the number of nodes
stack<pair<TreeNode*, bool> > s;  // the boolean variable denotes whether this node is visited or not
s.push(make_pair(root, false));  // initialize the stack
while(!s.empty()){
pair<TreeNode*, bool> p;
p = s.top();
s.pop();
if( p.first == NULL ){
continue;
}
if( p.second == true ){  // visited, output
count++;
if( count == k ){
min = p.first->val;
break;
}
if( min < p.first->val ){ // record minimum number
min = p.first->val;
}
continue;
}
else{
s.push(make_pair(p.first->right, false));   // note, this is slightly different from the recursive inorder traversal implementation
s.push(make_pair(p.first,true));
s.push(make_pair(p.first->left,false));
}
}
return min;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.