Python concise solution (O(lgn) space and O(1) time).

  • 3
    # @param root, a binary search tree's root node
    def __init__(self, root):
        self.stack = []
    def helper(self, root):
        while root:
            root = root.left
    # @return a boolean, whether we have a next smallest number
    def hasNext(self):
        return self.stack  # or self.stack != []
    # @return an integer, the next smallest number
    def next(self):
        node = self.stack.pop()
        return node.val

  • 0

    hey caikehe, can you explain why next() is O(1)? To me, it should be O(log n) because of the while loop in helper function.

  • 0

    Yes, the average time complexity is O(1), you can see, somtimes node.right even can be None. As the total number of nodes in a tree is n, so the number of node.right can't be larger than n, and next() can be called n times, so the amortized time complexity is O(1).

Log in to reply

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