# Java 5 ms Morris Traversal Solution: average O(1) time & O(1) space

• 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;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.