C++. using stack.


  • 12
    H
    /**
     * Definition for binary tree
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class BSTIterator {
    private:
        TreeNode *current = NULL; 
        stack<TreeNode*> s;
    public:
        BSTIterator(TreeNode *root) {
             // initialize the current pointer
            current = root;
        }
    
        /** @return whether we have a next smallest number */
        bool hasNext() {
            while(current){
                s.push(current);
                current = current->left;
            }
            if(s.empty()){
                return false;
            }
            return true;
        }
    
        /** @return the next smallest number */
        int next() {
            TreeNode* node = s.top();
            s.pop();
            current = node->right;
            return node->val;
        }
    };
    
    /**
     * Your BSTIterator will be called like this:
     * BSTIterator i = BSTIterator(root);
     * while (i.hasNext()) cout << i.next();
     */
    

    The basic idea behind this solution is that we have to implement inorder iteratively but it will gets split into two functions i.e. hasNext and next.
    hasNext() will push all the left elements and check and return accordingly if elements are in the stack.
    next() will just pop() the top element from the stack and update the current pointer to right .
    For this we are taking a stack and a current pointer.
    But maybe I may be wrong in hasNext as the requirement of question is O(1) for hasNext() as well.

    Open for comments.


  • 5
    W

    I think your code will probably return wrong value if I don't call hasNext() before I call next().

    My idea is keeping the top element of the stack to be the "next" one.

    When next() is called, return the top one and then find the "next" one.

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

  • 0
    Z

    you should not force people to call hasNext()


Log in to reply
 

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