My C++ Stack Solution


  • 1
    G

    Use a stack to keep track of the roots of the subtrees that haven't been completely explored, initializing it with the roots of the subtrees in the path to the leftmost node.

    class BSTIterator {
    public:
    stack<TreeNode *> toCheck;
    TreeNode * curr;
    BSTIterator(TreeNode *root) {
        // Initiate the Stack with the path to the leftmost node
        curr = NULL;
        get_leftmost(root);
    }
    
    /** @return whether we have a next smallest number */
    bool hasNext() {
        return (curr != NULL && curr->right != NULL) || !toCheck.empty(); 
    }
    
    /** @return the next smallest number */
    int next() {
        if (curr != NULL && curr->right != NULL) {
            get_leftmost(curr->right);
            if (!toCheck.empty()) {
                curr = toCheck.top();
                toCheck.pop();
            }
        } else {
            curr = toCheck.top();
            toCheck.pop();
        }
        
        return curr->val;
    }
    
    void get_leftmost(TreeNode * node){
        TreeNode * ptr;
        ptr = node;
        while(ptr != NULL) {
            toCheck.push(ptr);
            ptr = ptr->left;
        }
    }
    

    };


  • 0
    Y

    I think function next() is O(h) as it will invoke get_leftmost function


Log in to reply
 

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