The Binary Search Tree Iterator II problem asks you to implement a bidirectional iterator for a binary search tree (BST). You are provided with the root node of a BST, and you need to design a class with the following capabilities:
hasNext(): Returns true if there is a next smallest number in the in-order traversal of the BST.next(): Returns the next smallest number in the in-order traversal.hasPrev(): Returns true if there is a previous number in the in-order traversal.prev(): Returns the previous number in the in-order traversal.
The iterator should support moving forwards and backwards through the BST's in-order traversal. You must not reuse elements or skip any; each call to next() or prev() should move the iterator by exactly one element.
The BST is not modified during iteration, and you can assume the tree is valid. There is only one valid order: the in-order traversal. Efficiency is important, especially for large trees.
The problem is a twist on the classic BST iterator, which usually only supports forward in-order traversal. Here, we need to support both forward (next()) and backward (prev()) movement efficiently.
The brute-force approach is to perform a full in-order traversal up front, store the result in a list, and use an index to move back and forth. This gives O(1) time for next() and prev() but uses O(N) space.
A more memory-efficient approach is to simulate the traversal using a stack, as in the classic BST iterator. However, supporting prev() complicates things: we need to remember previously visited nodes to move backward. Therefore, we must balance space and efficiency, perhaps by combining a stack (for forward traversal) and a list (for history).
The key insight is that we can use a list to store visited nodes (history), and a stack to manage forward traversal. This hybrid approach allows both forward and backward movement with acceptable space and time complexity.
Let's break down the solution step by step:
history to store the values we've seen so far, and an integer index to track our current position in this list.index + 1 is less than the length of history, we can move forward in the history and increment index.history.index.true if either index + 1 is less than history length (we can move forward in history), or if the stack is not empty (there are more nodes to traverse).index is greater than 0, decrement index and return the value at the new position.true if index is greater than 0.This approach uses O(h) space for the stack (where h is the tree height) and O(N) space for the history in the worst case, but only as much as needed for the traversed nodes. All operations are O(1) amortized except when traversing forward for new nodes.
Let's use the following BST as an example:
7
/ \
3 15
/ \
9 20
The in-order traversal is: [3, 7, 9, 15, 20]
history = [], index = -1.next(): traverse left to 3, add 3 to history, index = 0, return 3.next(): move up to 7, add 7 to history, index = 1, return 7.next(): move right to 15, go left to 9, add 9 to history, index = 2, return 9.next(): back to 15, add 15 to history, index = 3, return 15.next(): right to 20, add 20 to history, index = 4, return 20.hasNext(): stack is empty, index + 1 = 5 equals history.length, so returns false.prev(): index = 3, return 15.prev(): index = 2, return 9.hasPrev(): index = 2 > 0, returns true.This shows how the iterator moves forward and backward through the BST efficiently.
Brute-Force Approach:
next() and prev() (array access).next() and prev(): O(1) amortized (since each node is processed once).hasNext() and hasPrev(): O(1).The solution is efficient for both time and space, with operations close to optimal for BST traversal with bidirectional support.
The Binary Search Tree Iterator II problem extends the classic BST iterator to support both forward and backward traversal in in-order sequence. By combining a stack (for forward traversal) and a history list (for backward movement), we achieve efficient, intuitive iteration. The approach balances time and space efficiency, making it suitable for large BSTs and frequent bidirectional traversal.
class BSTIterator:
def __init__(self, root):
self.stack = []
self.history = []
self.idx = -1
self._push_left(root)
def _push_left(self, node):
while node:
self.stack.append(node)
node = node.left
def hasNext(self):
return self.idx + 1 < len(self.history) or self.stack
def next(self):
self.idx += 1
if self.idx == len(self.history):
node = self.stack.pop()
self.history.append(node.val)
self._push_left(node.right)
return self.history[self.idx]
def hasPrev(self):
return self.idx > 0
def prev(self):
self.idx -= 1
return self.history[self.idx]
class BSTIterator {
public:
stack<TreeNode*> stk;
vector<int> history;
int idx = -1;
BSTIterator(TreeNode* root) {
pushLeft(root);
}
void pushLeft(TreeNode* node) {
while (node) {
stk.push(node);
node = node->left;
}
}
bool hasNext() {
return idx + 1 < (int)history.size() || !stk.empty();
}
int next() {
++idx;
if (idx == history.size()) {
TreeNode* node = stk.top(); stk.pop();
history.push_back(node->val);
pushLeft(node->right);
}
return history[idx];
}
bool hasPrev() {
return idx > 0;
}
int prev() {
--idx;
return history[idx];
}
};
class BSTIterator {
private Stack<TreeNode> stack = new Stack<>();
private List<Integer> history = new ArrayList<>();
private int idx = -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 idx + 1 < history.size() || !stack.isEmpty();
}
public int next() {
idx++;
if (idx == history.size()) {
TreeNode node = stack.pop();
history.add(node.val);
pushLeft(node.right);
}
return history.get(idx);
}
public boolean hasPrev() {
return idx > 0;
}
public int prev() {
idx--;
return history.get(idx);
}
}
class BSTIterator {
constructor(root) {
this.stack = [];
this.history = [];
this.idx = -1;
this.pushLeft(root);
}
pushLeft(node) {
while (node) {
this.stack.push(node);
node = node.left;
}
}
hasNext() {
return this.idx + 1 < this.history.length || this.stack.length > 0;
}
next() {
this.idx += 1;
if (this.idx === this.history.length) {
const node = this.stack.pop();
this.history.push(node.val);
this.pushLeft(node.right);
}
return this.history[this.idx];
}
hasPrev() {
return this.idx > 0;
}
prev() {
this.idx -= 1;
return this.history[this.idx];
}
}