First. Problem’s Description

Second. Problem’s Solution

BST has a non-decreasing inorder-traversing series. We can use a list to store the nodes and where we call next(), we delete the beginning node in the list.

Three. Code For Solution

class BSTIterator {
   
private:
    list<TreeNode*> lst;
public:
    BSTIterator(TreeNode* root) {
   
        if(root){
   
            TreeNode* p = root;
            stack<TreeNode*> s;
            while(!s.empty() || p){
   
                while(p){
   
                    s.push(p);
                    p = p->left;
                }
                if(!s.empty()){
   
                    p = s.top();
                    s.pop();
                    lst.push_back(p);
                    p = p->right;
                }
            }
        }
    }
    
    /** @return the next smallest number */
    int next() {
   
        auto ret = *(lst.begin());
        lst.pop_front();
        return ret->val;
    }
    
    /** @return whether we have a next smallest number */
    bool hasNext() {
   
        return lst.size() > 0;
    }
};

Four. Processing Results