/*
 * 演算法 / Algorithm:
 * 用一個堆疊延遲進行中序走訪。pushLeft 把某節點及其整條左子鏈壓入堆疊，
 * 讓堆疊頂端永遠是下一個要訪問的最小節點。next() pop 頂端並對其右子做 pushLeft。
 * We drive an in-order traversal lazily with a stack: pushLeft pushes a node and
 * its entire left spine so the top is always the next value; next() pops it and
 * pushLeft's its right child. Space O(h), amortized O(1) per next().
 */

// LeetCode 已定義 struct TreeNode（含 val、left、right）/ TreeNode is predefined by LeetCode.

typedef struct {
    struct TreeNode** stack; // 存節點指標的動態陣列，當作堆疊 / dynamic array of node pointers used as a stack
    int top;                 // 堆疊頂端索引：-1 表示空 / index of top element; -1 means empty
} BSTIterator;

// 輔助函式：從 node 開始，沿左子鏈全部壓入堆疊 / Helper: push node and its whole left spine.
void pushLeft(BSTIterator* it, struct TreeNode* node) {
    while (node != NULL) {          // 只要還有節點就繼續往左 / keep going while a node exists
        it->top++;                  // 頂端上移一格，指向新的寫入位置 / advance top to the next slot
        it->stack[it->top] = node;  // 把目前節點存入堆疊頂端 / store current node on top
        node = node->left;          // 移到左子，準備下一次壓入 / descend to the left child
    }
}

BSTIterator* bSTIteratorCreate(struct TreeNode* root) {
    // malloc 配置一塊 BSTIterator 大小的記憶體，回傳其指標 / allocate the iterator struct
    BSTIterator* it = (BSTIterator*)malloc(sizeof(BSTIterator));
    // 最多 10^5 個節點，配置足夠大的陣列當堆疊 / stack big enough for up to 1e5 nodes
    it->stack = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * 100000);
    it->top = -1;                   // 一開始堆疊為空 / start empty
    pushLeft(it, root);             // 建構時先壓入根的左子鏈 / seed with root's left spine
    return it;
}

int bSTIteratorNext(BSTIterator* it) {
    // 取出堆疊頂端節點：它就是下一個中序值 / pop the top node = next in-order value
    struct TreeNode* cur = it->stack[it->top];
    it->top--;                      // 頂端下移，等於彈出 / move top down = pop
    // 中序後繼在右子樹的最左處，故對右子做 pushLeft / successor is leftmost of right subtree
    pushLeft(it, cur->right);
    return cur->val;                // 回傳該節點的值 / return the popped node's value
}

bool bSTIteratorHasNext(BSTIterator* it) {
    return it->top >= 0;            // 頂端 >= 0 代表堆疊還有元素 / non-empty iff top >= 0
}

void bSTIteratorFree(BSTIterator* it) {
    free(it->stack);                // 先釋放內部陣列，避免記憶體洩漏 / free inner array first
    free(it);                       // 再釋放結構本身 / then free the struct
}

/**
 * 使用方式 / Usage:
 * BSTIterator* obj = bSTIteratorCreate(root);
 * int param_1 = bSTIteratorNext(obj);
 * bool param_2 = bSTIteratorHasNext(obj);
 * bSTIteratorFree(obj);
 */