Use a stack to simulate inorder traversal on demand:
class BSTIterator:
constructor(root):
this.stack = []
this._pushLeft(root)
function _pushLeft(node):
while node:
this.stack.append(node)
node = node.left
function next():
node = this.stack.pop()
this._pushLeft(node.right)
return node.val
function hasNext():
return this.stack.length > 0
The stack holds the "path to current position." After returning a node, you push its right subtree's left spine.
Time: average for next() (each node pushed/popped exactly once across all calls).
Space: for the stack.