requirements

Implement a binary search tree iterator class BSTIterator, representing an iterator that traverses a binary search tree (BST) in middle order:

  • BSTIterator(TreeNode root) Initializes an object of the BSTIterator class. The root node of BST, root, is given as part of the constructor. Pointer should be initialized to a number that does not exist in BST and is smaller than any element in BST.
  • Boolean hasNext() returns true if a number exists when traversing to the right of the pointer; Otherwise return false.
  • Int next() moves the pointer to the right and returns the number at the pointer.

Note that the pointer is initialized to a number that does not exist in the BST, so the first call to next() returns the smallest element in the BST.

You can assume that the next() call is always valid, that is, when next() is called, there is at least one next number in the middle-order traversal of the BST.

Example:

Input [BSTIterator ", "" next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"] [[[7, 3, 15, 9, null, null, 20]], [], [], [], [], [], [], [], [], [[]] output null, 3, 7, 9, true, true, 15, true, 20. False] BSTIterator BSTIterator = new BSTIterator([7, 3, 15, NULL, NULL, 9, 20]); bSTIterator.next(); // return 3 bstiterator.next (); // return 7 bstiterator.hasnext (); // Return True bstiterator.next (); // return 9 bstiterator.hasnext (); // Return True bstiterator.next (); // return 15 bstiterator.hasnext (); // Return True bstiterator.next (); // return 20 bstiterator.hasnext (); / / returns FalseCopy the code

The core code

class TreeNode:
    def __init__(self, val=0, left=None, right=None) :
        self.val = val
        self.left = left
        self.right = right
        
class BSTIterator:
    def __init__(self, root: TreeNode) :
        self.res = []
        def inorder(root) :
            if not root:
                return []
            return inorder(root.left) + [root.val] + inorder(root.right)
        self.res = inorder(root)
        self.index = 0

    def next(self) - >int:
        self.index += 1
        return self.res[self.index - 1]

    def hasNext(self) - >bool:
        return self.index < len(self.res)

# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.next()
# param_2 = obj.hasNext()
Copy the code

Another solution

class BSTIterator(object) :
    def __init__(self, root) :
        self.stack = []
        self.pushLeft(root)
 
    def next(self) :
        popedNode = self.stack.pop()
        self.pushLeft(popedNode.right)
        return popedNode.val
 
    def hasNext(self) :
        return len(self.stack) ! =0
    
    def pushLeft(self, node) :
        while(node):
            self.stack.append(node)
            node = node.left
Copy the code

We can use the middle order traversal to get the ordered list. The second solution: we use the stack to store the nodes.