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

  • 0

    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
                root.right = self.prev
                self.prev = 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.