https://leetcode.com/problems/binary-search-tree-iterator/description/

Tag: Tree Traversal, Stack,

Key Point:

Method 1: Traverse in creation

1. A list to store the nodes in-orderly and an index for current position
2. Construct the queue when initiated the iterator, traverse the tree and fill the node.

Method 2: Traverse at next()

1. A queue to store nodes which could have right-child
2. calling next() will not only return the node, but also process its right branch and push eligible right children back to the queue

Solution:

class BSTIterator:
    def __init__(self, root: Optional[TreeNode]):
        self.nums = []
        self.current = 0
        queue = deque()
        while root:
            queue.append(root)
            root = root.left

        while queue:
            node = queue.pop()
            self.nums.append(node.val)
            node = node.right
            while node:
                queue.append(node)
                node = node.left

    def next(self) -> int:
        self.current += 1
        return self.nums[self.current - 1]

    def hasNext(self) -> bool:
        return self.current < len(self.nums)

/

class BSTIterator:
    def __init__(self, root: Optional[TreeNode]):
        self.queue = deque()
        while root:
            self.queue.append(root)
            root = root.left

    def next(self) -> int:
        node = self.queue.pop()
        res = node.val
        node = node.right
        while node:
            self.queue.append(node)
            node = node.left
        return res

    def hasNext(self) -> bool:
        return len(self.queue) != 0