struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class BSTIterator
{
public:
    BSTIterator(TreeNode *root)
    {
        TreeNode *cur = root;
        while (cur)
        {
            st.push(cur);
            cur = cur->left;
        }
    }

    /** @return whether we have a next smallest number */
    bool hasNext()
    {
        return !st.empty();
    }

    /** @return the next smallest number */
    int next()
    {
        TreeNode *next = st.top();
        TreeNode *cur = next->right;
        st.pop();
        while (cur)
        {
            st.push(cur);
            cur = cur->left;
        }
        return next->val;
    }

private:
    stack<TreeNode *> st;
};