173. Binary Search Tree Iterator

Design an iterator over a binary search tree with the following rules:

• Elements are visited in ascending order (i.e. an in-order traversal)
• next() and hasNext() queries run in O(1) time on average.

Example

Example 1

Input:  {10,1,11,#,6,#,12}
Output:  [1, 6, 10, 11, 12]
Explanation:
The BST is look like this:
  10
  /\
 1 11
  \  \
   6  12
You can return the inorder traversal of a BST [1, 6, 10, 11, 12]

Example 2

Input: {2,1,3}
Output: [1,2,3]
Explanation:
The BST is look like this:
  2
 / \
1   3
You can return the inorder traversal of a BST tree [1,2,3]

Challenge

Extra memory usage O(h), h is the height of the tree.

Super Star: Extra memory usage O(1)

Method 1:

1. /** 
2.  * Definition for a binary tree node. 
3.  * struct TreeNode { 
4.  *     int val; 
5.  *     TreeNode *left; 
6.  *     TreeNode *right; 
7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {} 
8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} 
9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} 
10.  * }; 
11.  */  
12. class BSTIterator {  
13. private:  
14.     stack<TreeNode*> st;  
15. public:  
16.     BSTIterator(TreeNode* root) {  
17.         TreeNode *dummy = new TreeNode(0);  
18.         dummy->right = root;  
19.         st.push(dummy);  
20.         next();  
21.     }  
22.       
23.     /** @return the next smallest number */  
24.     int next() {  
25.         TreeNode* node = st.top();  
26.         st.pop();  
27.           
28.         TreeNode* root = node;  
29.         if (root->right != NULL) {  
30.             root = root->right;  
31.             while (root != NULL) {  
32.                 st.push(root);  
33.                 root = root->left;  
34.             }  
35.         }   
36.           
37.         return node->val;  
38.     }  
39.       
40.     /** @return whether we have a next smallest number */  
41.     bool hasNext() {  
42.         return (!st.empty());  
43.     }  
44. };  
45.   
46. /** 
47.  * Your BSTIterator object will be instantiated and called as such: 
48.  * BSTIterator* obj = new BSTIterator(root); 
49.  * int param_1 = obj->next(); 
50.  * bool param_2 = obj->hasNext(); 
51.  */  

Method 2:

1. /** 
2.  * Definition of TreeNode: 
3.  * class TreeNode { 
4.  * public: 
5.  *     int val; 
6.  *     TreeNode *left, *right; 
7.  *     TreeNode(int val) { 
8.  *         this->val = val; 
9.  *         this->left = this->right = NULL; 
10.  *     } 
11.  * } 
12.  * Example of iterate a tree: 
13.  * BSTIterator iterator = BSTIterator(root); 
14.  * while (iterator.hasNext()) { 
15.  *    TreeNode * node = iterator.next(); 
16.  *    do something for node 
17.  */  
18.   
19.   
20. class BSTIterator {  
21. private:  
22.     stack<TreeNode*> st;  
23.     TreeNode* currNode;  
24. public:  
25.     /* 
26.     * @param root: The root of binary tree. 
27.     */BSTIterator(TreeNode * root) {  
28.         // do intialization if necessary  
29.         currNode = root;  
30.     }  
31.   
32.     /* 
33.      * @return: True if there has next node, or false 
34.      */  
35.     bool hasNext() {  
36.         // write your code here  
37.         return currNode != NULL || !st.empty();  
38.     }  
39.   
40.     /* 
41.      * @return: return next node 
42.      */  
43.     TreeNode * next() {  
44.         // write your code here  
45.         while (currNode != NULL) {  
46.             st.push(currNode);  
47.             currNode = currNode->left;  
48.         }  
49.           
50.         currNode = st.top();  
51.         st.pop();  
52.           
53.         TreeNode *node = currNode;  
54.         currNode = currNode->right;  
55.           
56.         return node;  
57.     }  
58. };  

Method 3:

1. /** 
2.  * Definition of TreeNode: 
3.  * class TreeNode { 
4.  * public: 
5.  *     int val; 
6.  *     TreeNode *left, *right; 
7.  *     TreeNode(int val) { 
8.  *         this->val = val; 
9.  *         this->left = this->right = NULL; 
10.  *     } 
11.  * } 
12.  * Example of iterate a tree: 
13.  * BSTIterator iterator = BSTIterator(root); 
14.  * while (iterator.hasNext()) { 
15.  *    TreeNode * node = iterator.next(); 
16.  *    do something for node 
17.  */  
18.   
19.   
20. class BSTIterator {  
21. private:  
22.     vector<TreeNode*> sorted;  
23.     int index;  
24. public:  
25.     /* 
26.     * @param root: The root of binary tree. 
27.     */BSTIterator(TreeNode * root) {  
28.         // do intialization if necessary  
29.         index = -1;  
30.           
31.         inOrder(root, sorted);  
32.     }  
33.       
34.     void inOrder(TreeNode* root, vector<TreeNode*> &sorted) {  
35.         if (!root) return;  
36.           
37.         inOrder(root->left, sorted);  
38.         sorted.push_back(root);  
39.         inOrder(root->right, sorted);  
40.     }  
41.   
42.     /* 
43.      * @return: True if there has next node, or false 
44.      */  
45.     bool hasNext() {  
46.         // write your code here  
47.         return index + 1 < sorted.size();  
48.     }  
49.   
50.     /* 
51.      * @return: return next node 
52.      */  
53.     TreeNode * next() {  
54.         // write your code here  
55.         return sorted[++index];  
56.     }  
57. };