Simple C++ stack solution


  • 1
    class BSTIterator {
    private:
        stack<TreeNode*> sk;
        void consume( TreeNode* root ) {
            while( root ) {
                sk.push(root);
                root = root->left;
            }
        }
    public:
        BSTIterator(TreeNode *root) {
            consume(root);
        }
    
        bool hasNext() {
            return !sk.empty();
        }
    
        int next() {
            TreeNode* p = sk.top(); sk.pop();
            consume(p->right);
            return p->val;
        }
    };
    

  • 0

    The function consume seems to have O(h) time complexity instead of O(1), so next will have the same time complexity as well. Am I missing something?


  • 0

    Never mind my previous message. The problem requires AVERAGE time complexity as O(1), not worse case time complexity.


Log in to reply
 

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