Iterator in BST

The core idea is simple, you have a pushLeft, on ctor you pushLeft(root) then the next is always the stack top. Once you pop a top, pushLeft(right)

class BSTIterator {
private:
    vector<TreeNode*> stack;
    void pushLeft(TreeNode* root) {
        while (root) {
            stack.push_back(root);
            root = root->left;
        }
    }
 
public:
    BSTIterator(TreeNode* root) { pushLeft(root); }
 
    int next() {
        auto ret = stack.back();
        stack.pop_back();
        pushLeft(ret->right);
        return ret->val;
    }
 
    bool hasNext() { return !stack.empty(); }
};

Some problems

Problems are basically application of that iterator to do stuff

• two sum in bst
• merge two bsts in sorted list