Dare2Solve
The BSTIterator
class provides an iterator interface for a Binary Search Tree (BST). It allows iterating over the nodes of the BST in ascending order of their values.
To efficiently iterate over the BST in ascending order without using extra space proportional to the size of the tree, an iterative approach utilizing a stack is employed.
Initialization (__init__()
):
_leftmost_inorder()
to push all left children of the root onto the stack, ensuring the smallest element is at the top.Helper Method (_leftmost_inorder()
):
Next Smallest Element (next()
):
_leftmost_inorder()
on the right child to push its left children onto the stack.Has Next Element (hasNext()
):
next()
and hasNext()
operate in amortized O(1) time since each node is pushed and popped exactly once from the stack.This approach ensures efficient iteration over the BST while maintaining a space-efficient implementation.
class BSTIterator {
public:
BSTIterator(TreeNode* root) {
inorderTraversal(root);
}
int next() {
int val = nodes.front();
nodes.pop_front();
return val;
}
bool hasNext() {
return !nodes.empty();
}
private:
std::deque<int> nodes;
void inorderTraversal(TreeNode* node) {
if (!node) return;
inorderTraversal(node->left);
nodes.push_back(node->val);
inorderTraversal(node->right);
}
};
class BSTIterator:
def __init__(self, root: Optional[TreeNode]):
self.stack = []
self._leftmost_inorder(root)
def _leftmost_inorder(self, node):
while node:
self.stack.append(node)
node = node.left
def next(self) -> int:
topmost_node = self.stack.pop()
if topmost_node.right:
self._leftmost_inorder(topmost_node.right)
return topmost_node.val
def hasNext(self) -> bool:
return len(self.stack) > 0
class BSTIterator {
private List<Integer> nodes;
private Iterator<Integer> iterator;
public BSTIterator(TreeNode root) {
nodes = new ArrayList<>();
inorderTraversal(root);
iterator = nodes.iterator();
}
public int next() {
return iterator.next();
}
public boolean hasNext() {
return iterator.hasNext();
}
private void inorderTraversal(TreeNode node) {
if (node == null) return;
inorderTraversal(node.left);
nodes.add(node.val);
inorderTraversal(node.right);
}
}
var BSTIterator = function(root)
{
this.arr = [];
const go = (node) => {
if (!node) return;
go(node.left);
this.arr.push(node.val);
go(node.right);
}
go(root);
};
BSTIterator.prototype.next = function()
{
return this.arr.shift();
};
BSTIterator.prototype.hasNext = function()
{
return this.arr.length > 0;
};