173.Binary Search Tree Iterator

Tags: [iterator], [data_structure], [tree], [binary_tree], [BST], [binary_search_tree], [stack]

Com: {fb}

Link: https://leetcode.com/problems/binary-search-tree-iterator/\#/description

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Callingnext()will return the next smallest number in the BST.

Note:next()andhasNext()should run in average O(1) time and uses O(h) memory, wherehis the height of the tree.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

Solution: Stack

# 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
        """
        self.stack = []
        while root:
            self.stack.append(root)
            root = root.left


    def hasNext(self):
        """
        :rtype: bool
        """
        return len(self.stack) > 0


    def next(self):
        """
        :rtype: int
        """
        curr = self.stack.pop()
        tmp = curr.right
        while tmp:
            self.stack.append(tmp)
            tmp = tmp.left

        return curr.val

# Your BSTIterator will be called like this:
# i, v = BSTIterator(root), []
# while i.hasNext(): v.append(i.next())

Revelation:

• Be careful that we are using 'tmp = curr.right', not 'curr = curr.right', because we don't want to override the curr, which will be returned by the 'next' function.

Question:

• Why the average time complexity of 'next' = O(1)?