Binary Search Tree Iterator LeetCode solution in Python

1
# Definition for a binary tree node.
2
# class TreeNode:
3
#     def __init__(self, val=0, left=None, right=None):
4
#         self.val = val
5
#         self.left = left
6
#         self.right = right
7
class BSTIterator:
8

9
    def __init__(self, root: Optional[TreeNode]):
10
        self.root = root
11
        self.tree = []  # list to store the inorder traversal
12

13
        def inorder(node):
14
            if not node:
15
                return
16
            inorder(node.left)
17
            self.tree.append(node.val)
18
            inorder(node.right)
19
            return
20

21
        inorder(self.root)
22
        self.i = 0
23

24
    def next(self) -> int:
25
        self.i += 1
26
        return self.tree[self.i - 1]
27

28
    def hasNext(self) -> bool:
29
        return self.i - 1 < len(self.tree) - 1
30

31

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