Python solution based on inorder traversal

  • 1

    Notice that next() is required to have O(1), so the processing of finding is in hasNext()

    class BSTIterator(object):
    def __init__(self, root):
        self.root = root
        self.stack = []
        self.nxt = None
    def hasNext(self):
        while self.root:
            self.root = self.root.left
            if not self.stack:
                return False
            tmp = self.stack.pop()
            self.nxt = tmp.val
            self.root = tmp.right
        return True
    def next(self):
        return self.nxt

  • 0

    This is a good one! My solution is very similar to this one.

  • 0

    The wording in question is vague, but I think that contract of your solution doesn't conform to usual iterator contract.
    next should return new value each time

  • 0

    I agree, this is just the way to make it work on OJ. In an interview of course you should ask for clarifications.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.