Binary Search Tree Iterator

Problem Statement

Design an iterator for a binary search tree (BST). The iterator will be initialized with the root node of the BST.

Each call to getNext() should return the next smallest element in the BST in ascending order.

The iterator should provide a method hasMore() to indicate if there are more elements to retrieve.

Examples

BSTIter iter = new BSTIter(root);
iter.getNext();    // returns 4
iter.getNext();    // returns 8
iter.hasMore();    // returns true
iter.getNext();    // returns 10
iter.hasMore();    // returns true
iter.getNext();    // returns 16
iter.hasMore();    // returns true
iter.getNext();    // returns 22
iter.hasMore();    // returns false
    

Constraints

• Methods getNext() and hasMore() should operate on average in O(1) time complexity.
• The iterator should use O(h) memory, where h is the height of the BST.
• You can assume that getNext() will only be called when there is a next smallest element available.
• The number of nodes in the BST is between 1 and 10,000.