# Java Solution using Morris in-order traversal method: O(1) for space and O(1) for hasNext and amortized O(1) for next()

• I noticed that no one mentioned the Morris in-order traversal method so I posted it here. The memory space can be reduced to O(1). Also it's easy to get O(1) for hasNext() but not so obvious for next(). I didn't do a careful calculation of the time-complexity for next() method. But I believe it should be O(1) on average.

Here is the code:

``````public class BSTIterator {
TreeNode currNode;   // refer to the node currently having the smallest value
TreeNode preNode;    // auxiliary TreeNode variable

public BSTIterator(TreeNode root) {
preNode = root;
currNode = root;

// initialize the currNode to the node with the smallest value (basically the "leftmost" node)
if (currNode != null) {
while (currNode.left != null) {
preNode = currNode.left;   // go to the left subtree

while (preNode.right != null) {
preNode = preNode.right;    // find the "rightmost" node
}

preNode.right = currNode;   // modify the BST structure
currNode = currNode.left;   // and continue with the left subtree
}
}
}

public boolean hasNext() {
return currNode != null;    // if currNode is null, we reach the end of the BST
}

public int next() {
int currVal = currNode.val; // store the current smallest value to return later

// move currNode to refer to the next smallest value
currNode = currNode.right;  // start from the right child node of current node

while (currNode != null) {
if (currNode.left == null) {  // if the left child node is null, then we're done
break;
}

preNode = currNode.left;      // else we need to find the "rightmost" node of the left subtree

while (preNode.right != null && preNode.right != currNode) {
preNode = preNode.right;
}

if (preNode.right == null) {
preNode.right = currNode;  // we found the "rightmost" node, modify the BST structure
currNode = currNode.left;   // and continue with the left subtree

} else {
preNode.right = null;  // we are done with the left subtree, so restore the BST structure
break;
}
}

return currVal;    // return the smallest value saved earlier
}
}
``````

• This post is deleted!

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