Python simple solution using DFS and store all left side nodes in a list


  • 0

    Thanks RiqueZhang, you're correct!
    I shouldn't have stored all nodes at initialization, instead could store all left side nodes at once.

    class BSTIterator(object):
        def __init__(self, root):
            self.root = root
            self.stack = []
            if root:
                tmp = root
                while tmp:
                    self.stack.append(tmp)
                    tmp = tmp.left
    
        def hasNext(self):
            return self.stack
    
        def next(self):
            popped = self.stack.pop(-1)
            root = popped.right
            while root:
                self.stack.append(root)
                root = root.left
            
            return popped.val 
    

    Below is the original solution, which takes O(n) space complexity. I leave this for a reference of one bad pattern:-/

    class BSTIterator(object):
        def __init__(self, root):
            self.root = root
            self.curNode = root
            self.stack = []
            self.index = 0
            if root:
                self.DFS(self.root)
        
        def DFS(self, root):
            # traverse tree node by in-order 
            if root.left:
              self.DFS(root.left)  
            self.stack.append(root.val)
            if root.right:
                self.DFS(root.right)
          
    
        def hasNext(self):
            return self.index <= len(self.stack) - 1
    
        def next(self):
            returnedIndex = self.index
            self.index += 1
            return self.stack[returnedIndex]

  • 0
    R

    you have used O(N) space, not O(h) space. Bad answer.


Log in to reply
 

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