STL-and-Snippets/BST-Iterator.cpp at main · ADHIRAJ-12/STL-and-Snippets · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class BSTiterator{
    private:
    stack<TreeNode*> st;
    bool reverse = true;
    public:
    BSTiterator(TreeNode* root,bool flag){
        reverse = flag;
        pushAll(root);
    }

    int next(){
        TreeNode* temp = st.top();
        st.pop();

        if(reverse){
            pushAll(temp->left);
        }
        else{
            pushAll(temp->right);
        }

        return temp->val;
    }

    bool hasNext(){
        return !st.empty();
    }

    void pushAll(TreeNode* root){
        // while root not equal to null
        while(root){
            st.push(root);
            if(reverse){
                root = root->right;
            }
            else{
                root = root->left;
            }
        }
    }
};