The Morris Traversal time complexity for traversing all `n`

nodes is `O(n)`

, and the averaged time complexity for getting each node is `O(1)`

; the space complexity is `O(1)`

for storing only the current node. Using the Morris Traversal method to perform an inorder traversal on BST will generate the sorted array.

In this case, `next()`

function requires the next smallest element to be returned, so we break the traversing loop every time a node is traversed.

```
public class BSTIterator {
private TreeNode root,cur;
public BSTIterator(TreeNode root) {
root = root;
cur = root;
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
return cur != null;
}
/** @return the next smallest number */
public int next() {
int r = 0;
while(cur!=null){
if(cur.left==null){
r = cur.val;
cur = cur.right;
// Got the node, break loop
break;
}else{
TreeNode node = cur.left;
while(node.right!=null&&node.right!=cur){
node = node.right;
}
if(node.right==null){
node.right = cur;
cur = cur.left;
}else{
node.right = null;
r = cur.val;
cur = cur.right;
// Got the node, break loop
break;
}
}
}
return r;
}
}
```