C++ worst case O(1) time O(1) space solution, inspired by Morris Traversal


  • 0
    A

    Even in worst case, the time complexity of hasNext() and next() are both O(1). Not just average O(1), but constant O(1).
    The time complexity of constructor BSTIterator() is O(n). (Be aware: The problem doesn't have time complexity requirement on constructor.) Proper destructor is also provided.
    The space complexity is also O(1). No stack, no vector, no list, no queue, nothing.

    61 / 61 test cases passed
    Status: Accepted
    Runtime: 19 ms

    class BSTIterator {
    private:
        TreeNode *r, *h = NULL, *t = NULL;
    public:
        BSTIterator(TreeNode *root) {
            r = root;
            while (root) {
                if (TreeNode *p = root->left) {
                    while (p->right && p->right != root) p = p->right;
                    if (p->right) {
                        if (root->right && root->right->left) t = root;
                        else t = NULL;
                        root = root->right;
                    } else {
                        p->right = root;
                        root = root->left;
                    }
                } else {
                    if (!h) h = root;
                    if (t) t->right = root;
                    t = root;
                    root = root->right;
                }
            }
            t = h;
        }
    
        ~BSTIterator() {
            for( ; h; h = t) {
                t = h->right;
                if (h != r) h->left = NULL;
                if (t == r) h->right = NULL;
            }
        }
    
        bool hasNext() {
            return t;
        }
    
        int next() {
            int v = t->val;
            t = t->right;
            return v;
        }
    };
    

  • 1
    X

    but it actually change an BST into a "list", an Iterator should not change the original data structure. right?


  • 0
    A

    @xuyeiie Yes, but the problem doesn't say you can't touch the tree itself.
    Besides, all other iteration method doesn't support add node or delete node either, so the tree is static.


Log in to reply
 

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