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


  • 33
    Z
    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;
            }
        }
    };

  • 2
    C

    your hasNext() function could be more simple,like

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

    Other function could also be modified like that


  • 0
    A

    Perfect method. Very clear and stright forward.


  • 0
    G

    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?


  • 7
    D

    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
    H

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


  • 3
    2

    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
    Q

    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
    A

    @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
    P
    This post is deleted!

  • 0
    T

    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.


Log in to reply
 

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