Solution (via stack) + explanation ( of space & time complexity )


  • 0
    Y
    class BSTIterator {
    public:
        stack<TreeNode *>parents;
        BSTIterator(TreeNode *root) {
               
            while(root!=NULL) //add elements till you reach the leftmost element in the BST.
            {
               parents.push(root); // this will get space of O(LOG N) as we push the parents only.
               root=root->left;
            }
        }
    
        /** @return whether we have a next smallest number */
        bool hasNext() { 
            return !parents.empty();
        }
    
        /** @return the next smallest number */
        int next() {
            TreeNode * top= parents.top();
            int r=top->val;
            
            parents.pop();
            top=top->right;   //you need to check if the current smallest element has right elements before you go back to its parent.
    
         /* 
         loop Takes on worst-case complexity of O(LOG N ). The stress is on the keyword "average". 
        so it takes on AVERAGE O(1), Best O(1), and worst O(LOGN). Also it is important to highlight the difference isn't that big compared with O(1).
        for example, if the  the right sub tree is 1 Million elements so LOG (1M) = 20 ! so the difference isn't that much even in large # of elements.
        so On "AVG" we can accept this      */
    
            while(top!=NULL)  //add elements till you reach the leftmost element in this Sub BST.
            {
               parents.push(top); // this will get space of O(LOG N) as we push the parents only.
               top=top->left;
            }
            
            return r;
        }
    };
    
    
    

Log in to reply
 

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