BST Iterator Solution

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: $O(1)$ average for next() (each node pushed/popped exactly once across all calls).

Space: $O(h)$ for the stack.