class BSTIterator {
private:
stack<TreeNode*> st;
public:
BSTIterator(TreeNode *root) {
find_left(root);
}
/** @return whether we have a next smallest number */
bool hasNext() {
if (st.empty())
return false;
return true;
}
/** @return the next smallest number */
int next() {
TreeNode* top = st.top();
st.pop();
if (top>right != NULL)
find_left(top>right);
return top>val;
}
/** put all the left child() of root */
void find_left(TreeNode* root)
{
TreeNode* p = root;
while (p != NULL)
{
st.push(p);
p = p>left;
}
}
};
My Solution in C++, in average O(1) time and uses O(h) memory


@dequn when you traverse the tree using this next(), each edge of the tree has been visited at most twice, once cause' next(), once cause' find_left(). The whole edges of a tree is
n1
, supposed ann
node tree.
So average time of next() is2n / n = 2
, average time is O(1).

find_left is finding the smallest number by going to the extreme left and time it takes is the number of nodes present. so it is O(n) order, and it's being used inside the next function.
as I said here is a post whch explains this thing.
so next() is not O(1) time function.