Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.
Calling next() will return the next smallest number in the BST.
Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.
1)Solution:
Getting the next iterator is similarly to call the generator in the python. for the next smallest number, it‘s like the inorder tree traversal printed out (sorted order). we use stack the store the node visited while using iterators
so the next could pop the node in order from stack.
1 def __init__(self, root): 2 """ 3 :type root: TreeNode 4 """ 5 self.stk = [] 6 self.getAllLeftNode(root) 7 8 def hasNext(self): 9 """ 10 :rtype: bool 11 """ 12 13 return (len(self.stk) != 0) 14 15 def next(self): 16 """ 17 :rtype: int 18 """ 19 #pop from stack 20 node = self.stk.pop() 21 self.getAllLeftNode(node.right) 22 return node.val 23 24 def getAllLeftNode(self, node): 25 ‘‘‘ 26 get the most left nodes and put in the stack 27 ‘‘‘ 28 while (node is not None): 29 self.stk.append(node) 30 node = node.left