My Solution in C++, in average O(1) time and uses O(h) memory

  • 32
    class BSTIterator {
        stack<TreeNode*> st;
        BSTIterator(TreeNode *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 =;
            if (top->right != NULL)
            return top->val;
        /** put all the left child() of root */
        void find_left(TreeNode* root)
            TreeNode* p = root;
            while (p != NULL)
                p = p->left;

  • 2

    your hasNext() function could be more simple,like

    bool hasNext() {
           return !st.empty();

    Other function could also be modified like that

  • 0

    Perfect method. Very clear and stright forward.

  • 0

    I dont see the point of creating another function find_left() to look for the next smallest element. I agree with your algorithm, but the while loop in that function could be put into next() function, which could make the code to be more succinct.

  • 0

    But if you put it in there, then how can the constructor still use it?

  • 6

    Is next() in O(1) time? Since you call find_left() function in it, and there is a loop to find the min value.I think the average time of it won't be O(1).Or maybe I'm wrong.

  • 0

    nonono the standard is next() in O(h) memory and hasNext() in O(1) time

  • 3

    All the node will be pushed to the stack for only one time, so the average complexity of the next calling is O(1) amortized on single node .

  • 0

    Nice solution, but some code improvement. 1.if (pointer != NULL) can be change to if (pointer) //appears twice in your code 2. in the find_left function, it is unnecessary to define a temp pointer p, you can use root directly.

  • 0

    @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 n-1, supposed an n node tree.
    So average time of next() is 2n / n = 2, average time is O(1).

  • 0
    This post is deleted!

Log in to reply

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