My C++ Solution Using In-Order Traverse

• ``````/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class BSTIterator {
public:
vector<int> res;
int len;
void Traverse(TreeNode *root){
if(root == NULL)
return;
Traverse(root->left);
res.push_back(root->val);
Traverse(root->right);
/*if(root->left==NULL)
res.push_back(root->val);
else{
Traverse(root->left);
res.push_back(root->val);
}
if(root->right!=NULL)
Traverse(root->right);*/
}
BSTIterator(TreeNode *root) {
len = -1;
Traverse(root);
}

/** @return whether we have a next smallest number */
bool hasNext() {
len++;
if(len<res.size())
return true;
return false;
}

/** @return the next smallest number */
int next() {
return res[len];

}
};

/**
* Your BSTIterator will be called like this:
* BSTIterator i = BSTIterator(root);
* while (i.hasNext()) cout << i.next();
*/
``````

• @quitz54 You are using O(n) space while its clearly mentioned in the description to use O(h) space.
Hint : Use a stack ! :)

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