Clean short C++ solution with stack (In-Order Traversal)


  • 0

    Simply use In-Order traversal and keep the top of stack as the current smallest element in BST.

    private:
        stack<TreeNode*> s;
        void goAllWayLeft(TreeNode* nd) {
            while (nd) {
                s.push(nd);
                nd = nd->left;
            }
        }
    
    public:
    
        BSTIterator(TreeNode *r) {
            goAllWayLeft(r);
        }
    
        /** @return whether we have a next smallest number */
        bool hasNext() {
            return !s.empty();
        }
    
        /** @return the next smallest number */
        int next() {
            // safety check just in case next() is called before hasNext()
            if (s.empty()) return INT_MAX; 
            TreeNode* cur = s.top();
            s.pop();
            goAllWayLeft(cur->right);
            return cur->val;
        }
    

Log in to reply
 

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