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


  • 3
    C
    # @param root, a binary search tree's root node
    def __init__(self, root):
        self.stack = []
        self.helper(root)
        
    def helper(self, root):
        while root:
            self.stack.append(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()
        self.helper(node.right)
        return node.val

  • 0
    B

    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
    C

    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.