class BSTIterator:
    """
    @param: root: The root of binary tree.
    """
    def __init__(self, root):
        # do intialization if necessary
        self.root = root
        self._stack = []
        self._next(root)

    def _next(self, node):
        while node is not None:
            self._stack.append(node)
            node = node.left

    """
    @return: True if there has next node, or false
    """
    def hasNext(self, ):
        # write your code here
        return len(self._stack) > 0

    """
    @return: return next node
    """
    def next(self, ):
        # write your code here
        current = self._stack.pop()
        self._next(current.right)
        return current

class BSTIterator:
    """
    @param: root: The root of binary tree.
    """
    def __init__(self, root):
        # do intialization if necessary
        self.root = root
        self._stack = []
        self._next(root)

    def _next(self, node):
        while node is not None:
            self._stack.append(node)
            node = node.left

    """
    @return: True if there has next node, or false
    """
    def hasNext(self, ):
        # write your code here
        return len(self._stack) > 0

    """
    @return: return next node
    """
    def next(self, ):
        # write your code here
        current = self._stack.pop()
        self._next(current.right)
        return current

@param: root: The root of binary tree. # do intialization if necessary @return: True if there has next node, or false # write your code here @return: return next node # write your code here