173. Binary Search Tree Iterator

This is actually a iterative traversal of BST by the help of stack.

1:  /**  
2:   * Definition for binary tree  
3:   * struct TreeNode {  
4:   *   int val;  
5:   *   TreeNode *left;  
6:   *   TreeNode *right;  
7:   *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
8:   * };  
9:   */  
10:  class BSTIterator {  
11:  private:  
12:    stack<TreeNode *> stk;  
13:  public:  
14:    BSTIterator(TreeNode *root) {  
15:      while (root) {  
16:        stk.push(root);  
17:        root = root->left;  
18:      }  
19:    }  
20:    /** @return whether we have a next smallest number */  
21:    bool hasNext() {  
22:      return !stk.empty();  
23:    }  
24:    /** @return the next smallest number */  
25:    int next() {  
26:      TreeNode *t = stk.top();  
27:      stk.pop();  
28:      if (t->right) {  
29:        TreeNode *p = t->right;  
30:        while (p) {  
31:          stk.push(p);  
32:          p = p->left;  
33:        }  
34:      }  
35:      return t->val;  
36:    }  
37:  };  
38:  /**  
39:   * Your BSTIterator will be called like this:  
40:   * BSTIterator i = BSTIterator(root);  
41:   * while (i.hasNext()) cout << i.next();  
42:   */