Binary Search Tree Iterator

Problem: Binary Search Tree Iterator

The general idea is to first push root to stack inside our class. When we want to access next number, we check the top node of the stack. If the node has left child, then we try to find its leftmost node and push nodes along the path into the stack and assign those nodes' left pointer as null. If the node has no left child, we pop the node as we want and try to add its right child into the stack.

Code in Python:

# 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
        """
        if not root: self.stack = []
        else: self.stack = [root]


    def hasNext(self):
        """
        :rtype: bool
        """
        if self.stack: return True
        else: return False


    def next(self):
        """
        :rtype: int
        """
        node = self.stack[-1]
        while node.left:
            self.stack.append(node.left)
            node.left = None
            node = self.stack[-1]
        self.stack.pop()
        if node.right: self.stack.append(node.right)
        return node.val