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

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

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

Credits:

Special thanks to  for adding this problem and creating all test cases.

 

 to see which companies asked this question

 

class BSTIterator {private:    TreeNode *current = NULL;     stack
      
        s;public:    BSTIterator(TreeNode *root) {         // initialize the current pointer        current = root;    }    /** @return whether we have a next smallest number */    bool hasNext() {        while(current){            s.push(current);            current = current->left;        }        return !s.empty();    }    /** @return the next smallest number */    int next() {        TreeNode* node = s.top();        s.pop();        current = node->right;        return node->val;    }};