123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120

#include <iostream>
#include <vector>
#include <climits> 
#include <stack>
using namespace std;

    // Definition of TreeNode structure
    // for a binary tree node
struct TreeNode {
        // Value of the node
        int val;
        
        // Pointer to the left child node
        TreeNode* left;
        
        // Pointer to the right child node
        TreeNode* right;

        // Constructor to initialize the node with a
        // value and set left and right pointers to null
        TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    };

class BSTIterator {
        private:
            // Store inorder traversal
            vector<int> inorderTraversal; 
            // Pointer to track current index
            int pointer; 
            
            // Perform inorder traversal of the
            // BST and store in the array
            void inorder(TreeNode* root) {
                if (root == nullptr) return;
                inorder(root->left);
                inorderTraversal.push_back(root->val);
                inorder(root->right);
            }
        
public:
            // Constructor initializing the BSTIterator
            BSTIterator(TreeNode* root) {
                // Initialize pointer to
                // a non-existent value
                pointer = -1;
                // Store inorder traversal in the array
                inorder(root); 
            }
            
            // Checks if there exists a number in
            // the traversal to the right of the pointer
            bool hasNext() {
                return pointer + 1 < inorderTraversal.size();
            }
            
            // Moves the pointer to the right,
            // then returns the number at the pointer
            int next() {
                pointer++;
                return inorderTraversal[pointer];
            }
    };


    // Function to perform an in-order traversal
    // of a binary tree and print its nodes
    void printInOrder(TreeNode* root) {
        // Check if the current node
        // is null (base case for recursion)
        if (root == nullptr) {