Binary Search Tree Iterator Sequel - Facebook Top Interview Questions

                        Solution in C++ :

class BSTIterator {  // Time: O(1) amortized, in worst case O(H), Space: O(N)
    private:
    stack<Tree*> next_stack;
    vector<int> history;
    int index;

    public:
    BSTIterator(Tree* root) {
        index = -1;

        while (root) {
            next_stack.push(root);
            root = root->left;
        }
    }

    int next() {
        if (index + 1 < history.size()) {
            index++;  // Move to next element in history and return it
            return history[index];
        }

        Tree* next_node = next_stack.top();
        next_stack.pop();
        int value = next_node->val;

        next_node = next_node->right;
        while (next_node) {
            next_stack.push(next_node);
            next_node = next_node->left;
        }

        index++;
        history.push_back(value);
        return value;
    }

    bool hasnext() {
        return !next_stack.empty();
    }

    int prev() {
        // Move to previous element in history and return it
        index--;
        return history[index];
    }

    bool hasprev() {
        return index > 0;
    }
};
                    

                        Solution in Python : 
                            
class BSTIterator:
    def __init__(self, root):
        self.nodes, self.cur = [], -1
        # get nodes
        def dfs(root):
            if root:  # inorder -----Left Root Right----
                dfs(root.left), self.nodes.append(root.val), dfs(root.right)

        dfs(root)
        self.size = len(self.nodes)

    def next(self):
        self.cur += 1
        return self.nodes[self.cur] if self.cur < self.size else None

    def hasnext(self):
        return self.cur < self.size - 1

    def prev(self):
        self.cur -= 1
        return self.nodes[self.cur] if self.cur >= 0 else None

    def hasprev(self):
        return self.cur > 0