# 173-binary-search-tree-iterator


Try it on <a href='https://leetcode.com/problems/173-binary-search-tree-iterator'>leetcode</a>

## Description
<div class="description">

</div>

## Solution(Python)
```Python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class BSTIterator:
    def __init__(self, root: Optional[TreeNode]):
        self.itr = OptimalBSTIterator(root)

    def next(self) -> int:
        return self.itr.next()

    def hasNext(self) -> bool:
        return self.itr.hasNext()


# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.next()
# param_2 = obj.hasNext()

# Time Complexity: O(n)
# Space Complexity: O(n)
class NaiveBSTIterator:
    def __init__(self, root: Optional[TreeNode]):
        self.stack = []

        cur = root
        while cur:
            self.stack.append(cur)
            cur = cur.left

    def next(self) -> int:
        if len(self.stack) > 0:
            cur = self.stack.pop()
            if cur.right is not None:
                next_ = cur.right
                while next_:
                    self.stack.append(next_)
                    next_ = next_.left
            return cur.val
        else:
            return None

    def hasNext(self) -> bool:
        return len(self.stack) > 0


# Time Complexity: O(n)
# Space Complexity: O(1)
class OptimalBSTIterator:
    def __init__(self, root: Optional[TreeNode]):
        self.curr = root

    def next(self) -> int:
        if not self.hasNext():
            return None
        else:
            if self.curr.left is None:
                next_ = self.curr.val
                self.curr = self.curr.right
                return next_
            else:
                pred = self.curr.left

                while pred.right and pred.right != self.curr:
                    pred = pred.right

                if pred.right is None:
                    pred.right = self.curr
                    self.curr = self.curr.left
                else:
                    next_ = self.curr.val
                    pred.right = None
                    self.curr = self.curr.right
                    return next_
        return self.next()

    def hasNext(self) -> bool:
        return self.curr is not None

```