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


  • 32
    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?


  • 6
    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!

Log in to reply
 

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