# Share my two C++ solutions,and I'm not sure if the second solution meets the requirements

• Solution(1):

``````class BSTIterator {
public:

stack<TreeNode*> s;

BSTIterator(TreeNode *root) {
while (!s.empty())
s.pop();

while (root != NULL)
{
s.push(root);
root = root->left;
}
}

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

/** @return the next smallest number */
int next() {
TreeNode *cur = s.top();
s.pop();
int ret = cur->val;

cur = cur->right;

while (cur != NULL)
{
s.push(cur);
cur = cur->left;
}

return ret;
}
};
``````

Solution(2):

``````class BSTIterator {
public:
queue<TreeNode *> q;

BSTIterator(TreeNode *root) {
traversal(root);
}

void traversal(TreeNode *root) {
if (root == NULL)
return;

if (root->left != NULL)
traversal(root->left);

q.push(root);

if (root->right != NULL)
traversal(root->right);
}

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

/** @return the next smallest number */
int next() {
int number = q.front()->val;
q.pop();

return number;
}
};``````

• second solution does not meet the memory requirement. You have O(N), where N being number of nodes. It requires O(h) which is the heigh of the tree. Or O(log n) space, since the tree is a search tree, it must be balance.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.