The solutions I've seen so far use O(n) space, either for the recursion stack or for the self-managed stack. Here's an iterative inorder traversal version that only uses O(k) space by using a "stack" cut off at k elements. I called it `stac`

because of that and had to laugh when I then wrote `stac(k)`

:-)

**Solution 1, Python with deque(maxlen=k)**

Using a deque, setting its maximum length to k.

```
def kthSmallest(self, root, k):
stac = collections.deque(maxlen=k)
while True:
while root:
stac.append(root)
root = root.left
root = stac.pop()
if k == 1:
return root.val
k -= 1
root = root.right
```

**Solution 2, C++ with circular vector**

Using a vector of fixed size k and a stack pointer `i`

into it which will be used modulo k.

```
int kthSmallest(TreeNode* root, int k) {
vector<TreeNode*> stac(k);
int i = 0, j = k;
while (true) {
while (root) {
stac[i++%k] = root;
root = root->left;
}
root = stac[--i%k];
if (! --j)
return root->val;
root = root->right;
}
}
```

**Solution 3, C++ with deque**

I really like the previous version, but the fixed size `k`

isn't always necessary, so here's a version using a deque:

```
int kthSmallest(TreeNode* root, int k) {
deque<TreeNode*> stac;
while (true) {
while (root) {
stac.push_front(root);
while (stac.size() > k)
stac.pop_back();
root = root->left;
}
root = stac.front();
stac.pop_front();
if (! --k)
return root->val;
root = root->right;
}
}
```

And now I'm waiting for the Morris traversalists to show up...