https://leetcode.com/problems/binary-search-tree-iterator

In this question we are asked to perform Iterator, using inorder traversal, so let us just use inorder traversal, using stack: we will keep two global variables:

  1. self.stack: our explicit stack, where we keep our visited nodes.
  2. self.curr: current node we want to return during our traversal.

Next, what we do is perform usual iterative inorder traversal: we go als left as possible until we can and add nodes to stack. Then we remove node from stack and go to right children if it is possible. Also we save our out node, because we need to return it as output of next function. Finally, howe we can understand if we have next Node or not? If stack is not empty, we have it, also if current node is not None, we also have it, in other cases we are done.

Complexity: amortized time complexity of next function is O(1): we spend O(n) time to visit all n nodes. Note, that amortized time means, that we spend O(1) in average, it is exactly what we need in follow-up. Also space complexity for this solution is O(h): our stack will never be longer than height of our tree.

class BSTIterator:
    def __init__(self, root):
        self.stack = []
        self.curr = root
        
    def next(self):
        while self.curr:
            self.stack.append(self.curr)
            self.curr = self.curr.left
        self.curr = self.stack.pop()
        out = self.curr.val
        self.curr = self.curr.right
        return out

    def hasNext(self):
        return self.stack or self.curr

Note also, that there is Morris Traversal with O(1) time in average and O(1) space.

If you like the solution, you can upvote it on leetcode discussion section: Problem 0173