BinarySearch 0730 Binary Search Tree Iterator

Problem statement

https://binarysearch.com/problems/Binary-Search-Tree-Iterator/

Solution

Equal to Leetcode 0173. Binary Search Tree Iterator, but be careful with hasnext here.

Complexity

Amortized time is O(1), space is O(h).

Code

class BSTIterator:
    def __init__(self, root):
        self.stack = []
        self.curr = root
        
    def next(self):
        while self.curr:
            self.stack.append(self.curr)
            self.curr = self.curr.left
        self.curr = self.stack.pop()
        out = self.curr.val
        self.curr = self.curr.right
        return out

    def hasnext(self):
        return len(self.stack) != 0 or self.curr != None