Binary Search Tree Iterator

class BSTIterator:

    def __init__(self, root: Optional[TreeNode]):
        self.stk = []
        def rec(node):
            if not node:
                return None
            if node.right:
                rec(node.right)
            self.stk.append(node.val)
            if node.left:
                rec(node.left)
        rec(root)

    def next(self) -> int:
        return self.stk.pop()

    def hasNext(self) -> bool:
        return self.stk != []