173. Binary Search Tree Iterator

We can use a generator to do this. We make an in order traversal iterator and then call next on it.

class BSTIterator:
    def __init__(self, root: 'Optional[TreeNode]'):
        def inorder(node):
            if node:
                yield from inorder(node.left)
                yield node.val
                yield from inorder(node.right)
 
        # store the generator
        self.gen = inorder(root)
        self.buffer = None  # lookahead buffer
 
    def next(self) -> int:
        # if we already peeked, consume it
        if self.buffer is not None:
            val, self.buffer = self.buffer, None
            return val
        return next(self.gen)
 
    def hasNext(self) -> bool:
        if self.buffer is not None:
            return True
        try:
            self.buffer = next(self.gen)
            return True
        except StopIteration:
            return False

You can use the stack explicitly as well:

class BSTIterator:
    def __init__(self, root: Optional[TreeNode]):
        self.iter = self._inorder(root)
        self.nxt = next(self.iter, None)
 
    def _inorder(self, node: Optional[TreeNode]) -> Generator[int, None, None]:
        stack = []
        while node or stack:
            while node:
                stack.append(node)
                node = node.left
            node = stack.pop()
            yield node.val
            node = node.right
 
    def next(self) -> int:
        res = self.nxt
        self.nxt = next(self.iter, None)
        return res
 
    def hasNext(self) -> bool:
        return self.nxt is not None