# 173. Binary Search Tree Iterator
Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.
Calling next() will return the next smallest number in the BST.
Example:
BSTIterator iterator = new BSTIterator(root);
iterator.next(); // return 3
iterator.next(); // return 7
iterator.hasNext(); // return true
iterator.next(); // return 9
iterator.hasNext(); // return true
iterator.next(); // return 15
iterator.hasNext(); // return true
iterator.next(); // return 20
iterator.hasNext(); // return false
Note:
- next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.
- You may assume that next() call will always be valid, that is, there will be at least a next smallest number in the BST when next() is called.
# Solution
Approach 1: Stack.
# Code (Python)
Approach 1:
class InOrderIterator:
def __init__(self, root):
self.next = None
self.stack = []
node = root
while node:
self.stack.append(node)
node = node.left
self._set_next()
def get_next(self):
result = self.next
self._set_next()
return result.val
def _set_next(self):
if self.stack:
node = self.stack.pop()
self.next = node
node = node.right
while node:
self.stack.append(node)
node = node.left
else:
self.next = None
def has_next(self):
return self.next != None
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Code (C++)
Approach 1:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class BSTIterator {
private:
stack<TreeNode*> st;
public:
BSTIterator(TreeNode* root) {
TreeNode *curr = root;
while (curr)
{
st.push(curr);
curr = curr->left;
}
}
/** @return the next smallest number */
int next() {
TreeNode *node = st.top();
st.pop();
TreeNode *curr = node->right;
while (curr)
{
st.push(curr);
curr = curr->left;
}
return node->val;
}
/** @return whether we have a next smallest number */
bool hasNext() {
return !st.empty();
}
};
/**
* Your BSTIterator object will be instantiated and called as such:
* BSTIterator* obj = new BSTIterator(root);
* int param_1 = obj->next();
* bool param_2 = obj->hasNext();
*/