First of all, even with most optimized space and time complexity, I have to say this may be not the best solution, since it changes the tree structure a little bit during constructor period.

#Construct Period

The idea is use in-order Morris Tree Traversal (check out [1][2] if you are not familiar with it, otherwise the bellow explanation to you is nonsense) to construct a threaded binary tree in construct function. (This is O(n) time, but we don't care much about it.) Then set a pointer (we call it "curr") to the smallest TreeNode, which is easy to do, just find the left-most child from root.

#hasNext()

For hasNext() function, simple return "curr != null", which is by definition of threaded binary tree.

#next()

For next() function, it is a little bit tricky. We call the right child of "curr" as "next". If "next" is not a normal right child of "curr", which means the right child relationship is constructed during the threaded binary tree construction period, then the next TreeNode we should iterate is indeed "next". However, if "next" is a normal right child of "curr", then the next TreeNode we should iterate is actually the left-most child of "next".

So the problem reduces to how to make clear the situation. Well, it is no hard. If "next" is null, then we've done, simply set "curr" to null. If "next" has no left child, or "next"'s left child is strictly larger than "curr", that means it is a normal right child of "curr", so we should set "curr" to left-most child of "next". Otherwise, we set "curr" to "next", and break the right child relationship between "curr" and "next", to recover the original tree structure.

#Complexity analysis

The space complexity is straightforwardly O(1). The time complexity needs some more explanation. Since the only part that is not O(1) is when we search the left-most child of "next". However, for all the children along this left path (say, there are N children), we do once search left-most and (N-1) times simply go to right child. So the amortized time complexity is still O(1).

#Code:

```
public class BSTIterator {
private TreeNode curr;
public BSTIterator(TreeNode root) {
TreeNode prev;
//Do a morris in-order traversal, to construct a threaded binary tree
curr = root;
while(curr != null){
if(curr.left == null){
curr = curr.right;
}
else{
prev = curr.left;
while(prev.right != null && prev.right != curr)
prev = prev.right;
if(prev.right == null){
prev.right = curr;
curr = curr.left;
}
else{
curr = curr.right;
}
}
}
//get the left-most child of root, i.e. the smallest TreeNode
curr = root;
while(curr != null && curr.left != null)
curr = curr.left;
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
return curr != null;
}
/** @return the next smallest number */
public int next() {
//copy the value we need to return
int result = curr.val;
TreeNode next = curr.right;
if(next == null)
curr = next;
//the right child relationship is a normal one, find left-most
//child of "next"
else if(next.left == null || next.left.val > curr.val){
curr = next;
while(curr.left != null)
curr = curr.left;
}
//the right child relationship is made when we
//construct the threaded binary tree
else{
curr.right = null;//we recover the original tree structure
curr = next;
}
return result;
}
}
```

#Reference

For those who are not familiar with Morris Tree Traversal, these two paragraphs are good references.

[1]https://en.wikipedia.org/wiki/Threaded_binary_tree

[2]http://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/