Ascending Cursor Over a Search Tree

Implement a class BSTCursor that walks a binary search tree in ascending order, one value at a time:

• BSTCursor(root) prepares the cursor (the tree may be empty);
• next() returns the next smallest value not yet returned (only called when one exists);
• has_next() returns True if another value remains.

Tests drive the class with run_ops: the first operation constructs the object, and the result list holds None for the constructor.

Examples

    7
   / \
  3   15
     /  \
    9    20

ops  = ["BSTCursor", "next", "next", "has_next", "next", "next", "next", "has_next"]
args = [[build_tree([7, 3, 15, None, None, 9, 20])], [], [], [], [], [], [], []]
Output: [None, 3, 7, True, 9, 15, 20, False]

Constraints

• 0 <= number of nodes <= 3000
• next and has_next should run in amortised O(1) time using O(h) memory; do not copy the whole tree into a list

Goals

• Produce inorder values lazily, one per call
• Keep only O(h) memory by storing the pending left spine