Binary Search Tree Iterator LeetCode solution in C++

1
// TC O(1) and O(H) Space
2

3
// MIMIC inorder
4
class BSTIterator {
5
 public:
6
  stack<TreeNode *> stk;
7
  BSTIterator(TreeNode *root) {
8
    pushAll(root);
9
    // left is done
10
  }
11

12
  int next() {
13
    // root handled
14
    TreeNode *node = stk.top();
15
    int ans = node->val;
16
    stk.pop();
17

18
    // right handled
19
    pushAll(node->right);
20

21
    return ans;
22
  }
23

24
  bool hasNext() {
25
    return stk.size() != 0; // stk is empty then no next to show simple
26
  }
27

28
  void pushAll(TreeNode *root) {
29
    // left part - as inorder is like Left left left, once a root is done then
30
    // check right
31
    while (root != NULL) {
32
      stk.push(root);
33
      root = root->left;
34
    }
35
  }
36
};