C++ using stack, inorder/preorder/postorder


  • 0
    S

    Sorted order for BST = inorder traversal. The code may be slightly modified to make a postorder/preorder iterator.

    class BSTIterator {
    public:
        stack<pair<TreeNode*, int>> s;
    
        BSTIterator(TreeNode *root) {
            if (root != 0) s.push({root, 0});
            order();
        }
    
        /** @return whether we have a next smallest number */
        bool hasNext() {
            return !s.empty();
        }
    
        /** @return the next smallest number */
        int next() {
            auto p = s.top();
            s.pop();
            order();
            return p.second;
        }
        
        void order() {
            while (!s.empty()) {
                auto p = s.top();
                if (p.first == 0) break;
                s.pop();
                TreeNode* n = p.first;
                //s.push({0, n->val}); //postorder
                if (n->right != 0) s.push({n->right, 0});
                s.push({0, n->val}); //inorder
                if (n->left != 0) s.push({n->left, 0});
                //s.push({0, n->val}); //preorder
            }
        }
    };
    

Log in to reply
 

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