from utils.treeNode import TreeNode

class BSTIterator:
    # O(n) worst case for time and space
    def __init__(self, root):
        self.stack = []
        while root:
            self.stack.append(root)
            root = root.left
    
    # O(1) time and space
    def has_next(self):
        return len(self.stack) > 0
    
    #time: O(n) worst case, O(1) average
    # space: O(n) worst case, O(log n) if balanced
    def next(self):
        if not self.has_next():
            return None
        
        node = self.stack.pop()
        result = node.value

        if node.right:
            node = node.right
            
            while node:
                self.stack.append(node)
                node = node.left

        return result
       
