BST Iterator

Problem

Simulate an iterator over the inorder traversal of a binary search tree.

values are inserted in order into a BST (duplicates ignored). operations contains "next" and "has_next": next returns the next value in ascending order and has_next reports whether another value remains. Keep the left spine of the tree on a stack so each call is O(1) amortized.

Return the list of recorded results.

Hint

Initialize the stack with the left spine and refill it from the right child's left spine.

Test cases

case 1

in: [[7,3,15,9,20],["has_next","next","next","next","has_next","next","next","has_next"]]

expected: [true,3,7,9,true,15,20,false]

case 2

in: [[1],["next","has_next"]]

expected: [1,false]

case 3

in: [[],["has_next"]]

expected: [false]

case 4

in: [[2,1,3],["next","next","next"]]

expected: [1,2,3]

Starter codePython

def bst_iterator_ops(values, operations):
    # Your code here
    pass

4 test cases · run your code against them in the editor