Python solution with O(1) Space and O(h) time


  • 0
    Y
    # Definition for a  binary tree node
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class BSTIterator(object):
        
        
        def __init__(self, root):
            """
            :type root: TreeNode
            """
            self.node = root
                     
    
        def hasNext(self):
            """
            :rtype: bool
            """
            foundNext = False
            while self.node and not foundNext:
              if self.node.left:
                 prev = self.node.left
                 while prev.right and prev.right != self.node:
                    prev = prev.right
                 if prev.right:
                    prev.right = None
                    self.value = self.node.val
                    self.node = self.node.right
                    foundNext = True
                 else:
                    prev.right = self.node
                    self.node = self.node.left
              else:
                self.value = self.node.val
                self.node = self.node.right
                foundNext = True
                
            return foundNext    
    
        def next(self):
            """
            :rtype: int
            """
            return self.value
    
    # Your BSTIterator will be called like this:
    # i, v = BSTIterator(root), []
    # while i.hasNext(): v.append(i.next())

Log in to reply
 

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