Binary Search Tree Iterator II
Problem
Design an iterator over a binary search tree that walks values in in-order (ascending) and can move in both directions. Support next() and prev() to return the next or previous value, plus hasNext() and hasPrev() to test availability.
The iterator starts positioned before the first element, so the first next() returns the smallest value. We expand the tree lazily and cache values already produced so prev() can replay them without re-walking.
tree = [7,3,15,null,null,9,20]; ops = next, next, prev, next, hasNext3, 7, 3, 7, trueclass BSTIterator:
def __init__(self, root):
self.stack = []
self.arr = []
self.pos = -1
self._push_left(root)
def _push_left(self, node):
while node:
self.stack.append(node)
node = node.left
def hasNext(self):
return self.pos < len(self.arr) - 1 or bool(self.stack)
def next(self):
self.pos += 1
if self.pos == len(self.arr):
node = self.stack.pop()
self.arr.append(node.val)
self._push_left(node.right)
return self.arr[self.pos]
def hasPrev(self):
return self.pos > 0
def prev(self):
self.pos -= 1
return self.arr[self.pos]class BSTIterator {
constructor(root) {
this.stack = [];
this.arr = [];
this.pos = -1;
this.pushLeft(root);
}
pushLeft(node) {
while (node) { this.stack.push(node); node = node.left; }
}
hasNext() {
return this.pos < this.arr.length - 1 || this.stack.length > 0;
}
next() {
this.pos++;
if (this.pos === this.arr.length) {
const node = this.stack.pop();
this.arr.push(node.val);
this.pushLeft(node.right);
}
return this.arr[this.pos];
}
hasPrev() { return this.pos > 0; }
prev() { this.pos--; return this.arr[this.pos]; }
}class BSTIterator {
private Deque<TreeNode> stack = new ArrayDeque<>();
private List<Integer> arr = new ArrayList<>();
private int pos = -1;
public BSTIterator(TreeNode root) { pushLeft(root); }
private void pushLeft(TreeNode node) {
while (node != null) { stack.push(node); node = node.left; }
}
public boolean hasNext() {
return pos < arr.size() - 1 || !stack.isEmpty();
}
public int next() {
pos++;
if (pos == arr.size()) {
TreeNode node = stack.pop();
arr.add(node.val);
pushLeft(node.right);
}
return arr.get(pos);
}
public boolean hasPrev() { return pos > 0; }
public int prev() { pos--; return arr.get(pos); }
}class BSTIterator {
stack<TreeNode*> st;
vector<int> arr;
int pos = -1;
void pushLeft(TreeNode* node) {
while (node) { st.push(node); node = node->left; }
}
public:
BSTIterator(TreeNode* root) { pushLeft(root); }
bool hasNext() { return pos < (int)arr.size() - 1 || !st.empty(); }
int next() {
pos++;
if (pos == (int)arr.size()) {
TreeNode* node = st.top(); st.pop();
arr.push_back(node->val);
pushLeft(node->right);
}
return arr[pos];
}
bool hasPrev() { return pos > 0; }
int prev() { pos--; return arr[pos]; }
};Explanation
A one-direction BST iterator uses the controlled-recursion stack: push the leftmost spine, and each next() pops a node and pushes the left spine of its right child. That gives in-order values one at a time in O(1) amortized.
To support prev() we add a cache. Every value we ever produce is appended to a list arr, and a cursor pos points at the current position inside that list.
next() first advances pos. If pos reaches the end of the cache we need a genuinely new value, so we pop the stack, record it, and extend the spine. If pos is still inside the cache, the value was already computed — we just return it (this is how we move forward again after going back).
prev() simply decrements pos and returns the cached value. hasPrev() is pos > 0; hasNext() is true if the cursor is not at the end of the cache, or the stack still has unexpanded nodes.
Example on [7,3,15,null,null,9,20] (in-order 3,7,9,15,20): next→3, next→7 (both expand new nodes), prev→3 (cached), next→7 (cached again) — the cache lets us replay without touching the tree.