O(1) time for BOTH hasNext() and next(). O(1) space. Mutate the tree to linkedList


  • 0
    D

    Modify the tree in place into a sorted linkedlist. Use node.left as the next pointer for the next node in the linkedlist.
    Both hasNext() and next() will run in O(1) with the caveat that init will run in O(n)

    class BSTIterator(object):
        def __init__(self, root):
            """
            :type root: TreeNode
            """
            self.prev = None
            def mutate(root):
                if not root: return
                mutate(root.right)
                root.right = self.prev
                self.prev = root
                mutate(root.left)
            mutate(root)
            self.head = self.prev
    
        def hasNext(self):
            """
            :rtype: bool
            """
            return bool(self.head)
            
    
        def next(self):
            """
            :rtype: int
            """
            ans = self.head.val
            self.head = self.head.right
            return ans
    

Log in to reply
 

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