Below is the java solution.

At the first glance, the algorithm run in O(h) time & O(h) space. But if you take a closer look at the problem, you will see that it asks for "on average".

We see that, for the function next, each node is popped on to the stack exactly 1 time. Hence, on average, it is O(1) time complexity.

```
import java.util.Stack;
public class BSTIterator {
private Stack<TreeNode> stack;
public BSTIterator(TreeNode root) {
stack = new Stack<TreeNode>();
TreeNode tempNode = root;
if(root!=null) {
while(tempNode != null){
stack.push(tempNode);
tempNode = tempNode.left;
}
}
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
return !stack.empty();
}
/** @return the next smallest number */
public int next() {
TreeNode node = stack.pop();
TreeNode tempNode = node.right;
if(tempNode!=null){
while(tempNode!=null){
stack.push(tempNode);
tempNode = tempNode.left;
}
}
return node.val;
}
}
```