Similar problems: LC 285. Inorder Successor in BST, LC 230. Kth Smallest Element in a BST, LC 94. Binary Tree Inorder Traversal
A BST iterator performs an inorder traversal of the tree step-by-step. The idea is to basically perform a controlled inorder traversal of the tree. If you are familiar with the iterative inorder traversal of a binary tree, solving this question should be straightforward. If you are not familiar with it, consider reading my solution of LC 94. Binary Tree Inorder Traversal.
Quoting from my solution for the iterative inorder traversal (link above):
Starting from the given root node of the tree:
- Go as left as possible pushing the nodes in a stack (until the encountered node’s left child is NULL).
- Pop the node which is on top of the stack
- Push the node to the answer and check:
- if the node has a right child, push the right child to the stack and then go to step 1 (essentially we are now traversing the right subtree of the previous node as we have already visited the left subtree and also the root)
- else repeat step 2
We can clearly use the same idea to solve this question. The code below uses the same approach, more commonly known as controlled inorder traversal.
class BSTIterator {
public:
stack<TreeNode*> st;
BSTIterator(TreeNode* root) {
while (root) {
st.push(root);
root = root->left;
}
}
/** @return the next smallest number */
int next() {
if (!hasNext()) return -1;
TreeNode *t = st.top();
st.pop();
TreeNode* temp = t->right;
while (temp) {
st.push(temp);
temp = temp->left;
}
return t->val;
}
/** @return whether we have a next smallest number */
bool hasNext() {
if (st.empty()) return false;
return true;
}
};
Time complexity: next() has complexity O(h) where h is the height of tree, hasNext() has complexity O(1)
Space complexity: O(h)