LC 0173 [M] Binary Search Tree Iterator - ALawliet/algorithms GitHub Wiki

push all left

inorder traversal with a stack

1. take the left node and keep going left until you can't (because that's what inorder traversal does)
2. then pop a node take the right node and keep going left with that

---

class BSTIterator:


    def push_all_left(self, node):
        while node:
            self.stack.append(node)
            node = node.left


    def __init__(self, root: TreeNode):
        self.stack = []

        self.push_all_left(root)
        

    def next(self) -> int:
        """
        @return the next smallest number
        """
        node = self.stack.pop()
        self.push_all_left(node.right)
        return node.val
        

    def hasNext(self) -> bool:
        """
        @return whether we have a next smallest number
        """
        return len(self.stack) > 0