/*
 * 演算法 / Algorithm:
 * 用 std::stack 延遲中序走訪。pushLeft 壓入一個節點及其整條左子鏈，
 * 使堆疊頂端永遠是下一個中序節點。next() 取頂端並對其右子 pushLeft。
 * Lazy in-order traversal with a stack: pushLeft loads a node's left spine so the
 * top is the next value; next() pops it and pushLeft's its right child.
 * Space O(h), amortized O(1) per next().
 */

#include <stack>

// TreeNode 由 LeetCode 預先定義 / TreeNode is predefined by LeetCode.

class BSTIterator {
private:
    // std::stack 是後進先出容器；這裡存節點指標 / a LIFO container of node pointers
    std::stack<TreeNode*> st;

    // 把 node 及其整條左子鏈壓入堆疊 / push node and its entire left spine
    void pushLeft(TreeNode* node) {
        while (node != nullptr) {   // while 迴圈沿左子一路下走 / walk down the left children
            st.push(node);          // 壓入目前節點 / push current node onto the stack
            node = node->left;      // 移到左子 / move to the left child
        }
    }

public:
    // 建構子：初始化時壓入根的左子鏈 / constructor seeds root's left spine
    BSTIterator(TreeNode* root) {
        pushLeft(root);
    }

    int next() {
        TreeNode* cur = st.top();   // 讀取頂端節點：下一個中序值 / peek the next in-order node
        st.pop();                   // 彈出它 / remove it from the stack
        pushLeft(cur->right);       // 後繼在右子樹最左處 / successor lives in the right subtree
        return cur->val;            // 回傳其值 / return its value
    }

    bool hasNext() {
        return !st.empty();         // 堆疊非空就還有下一個 / more remain iff stack is non-empty
    }
};

/**
 * 使用方式 / Usage:
 * BSTIterator* obj = new BSTIterator(root);
 * int param_1 = obj->next();
 * bool param_2 = obj->hasNext();
 */