Even in worst case, the time complexity of `hasNext()`

and `next()`

are both O(1). Not just average O(1), but constant O(1).

The time complexity of constructor `BSTIterator()`

is O(n). (Be aware: The problem doesn't have time complexity requirement on constructor.) Proper destructor is also provided.

The space complexity is also O(1). No stack, no vector, no list, no queue, nothing.

*61 / 61 test cases passed*

*Status: Accepted*

*Runtime: 19 ms*

```
class BSTIterator {
private:
TreeNode *r, *h = NULL, *t = NULL;
public:
BSTIterator(TreeNode *root) {
r = root;
while (root) {
if (TreeNode *p = root->left) {
while (p->right && p->right != root) p = p->right;
if (p->right) {
if (root->right && root->right->left) t = root;
else t = NULL;
root = root->right;
} else {
p->right = root;
root = root->left;
}
} else {
if (!h) h = root;
if (t) t->right = root;
t = root;
root = root->right;
}
}
t = h;
}
~BSTIterator() {
for( ; h; h = t) {
t = h->right;
if (h != r) h->left = NULL;
if (t == r) h->right = NULL;
}
}
bool hasNext() {
return t;
}
int next() {
int v = t->val;
t = t->right;
return v;
}
};
```