My straight-forward solution in O(1) time and O(n) memory


  • -2
    R

    My thought was very straight-forward by doing all the heavy work in the constructor in which traverse the tree and save all node in in-order sequence. Thus all remaining task for hasNext() and next() is quite simple...

    But I doubt that this solution will persuade my interviewer! Ohhhhh!

    Any hints for a satisfactory solution?

    class BSTIterator {
    public:
        BSTIterator(TreeNode *root) {
            inorder(root);
        }
    
        /** @return whether we have a next smallest number */
        bool hasNext() {
            return !s.empty();
        }
    
        /** @return the next smallest number */
        int next() {
            int val = s.top()->val;
            s.pop();
            return val;
        }
    private:
        stack<TreeNode *> s;
        void inorder(TreeNode *root) {
            if (root) {
                if (root->right) inorder(root->right);
                s.push(root);
                if (root->left) inorder(root->left);
            }
        }
    };

  • 0
    Z

    It's obvious that this problem ask you to maintain some structure to traversal the tree .
    I guess a stack would be the correct idea.


  • 0
    D

    but what about additional memory during traversing the tree?


  • 0
    D

    You should use a stack to simulate the inorder traverse of this BST. Since the capacity of the stack equals to the depth of the BST, you will solve it in O(logn) space complexity.


  • 0
    J

    You may use lots of iterators of the same tree, so the less memory usage the better.


Log in to reply
 

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