C++, using stack and in-order traversal


  • 0
    H

    class BSTIterator {
    private:
    stack<TreeNode*> stk;
    TreeNode* pr;

    public:
    BSTIterator(TreeNode *root) { // do an inorder traversal

      pr = root; 
      while( pr != NULL)
       {
           stk.push(pr);
           pr = pr->left; 
           
       }
        
    }
        /** @return whether we have a next smallest number */
    bool hasNext() {
       
        return ( !stk.empty() || pr != NULL); 
        
    }
    
    /** @return the next smallest number */
    int next() {
       while( pr != NULL)
       {
           stk.push(pr);
           pr = pr->left; 
           
       }
       
       TreeNode* temp = stk.top();
       stk.pop();
       int valr = temp->val;
       pr = temp->right; 
       return valr; 
    }
    

    };


Log in to reply
 

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