Description
Implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (BST):
BSTIterator(TreeNode root)Initializes an object of theBSTIteratorclass. Therootof the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST.boolean hasNext()Returnstrueif there exists a number in the traversal to the right of the pointer, otherwise returnsfalse.int next()Moves the pointer to the right, then returns the number at the pointer.
Notice that by initializing the pointer to a non-existent smallest number, the first call to next() will return the smallest element in the BST.
You may assume that next() calls will always be valid. That is, there will be at least a next number in the in-order traversal when next() is called.
Examples:
Example 1:
Input
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
Output
[null, 3, 7, true, 9, true, 15, true, 20, false]
Explanation
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next(); // return 3
bSTIterator.next(); // return 7
bSTIterator.hasNext(); // return True
bSTIterator.next(); // return 9
bSTIterator.hasNext(); // return True
bSTIterator.next(); // return 15
bSTIterator.hasNext(); // return True
bSTIterator.next(); // return 20
bSTIterator.hasNext(); // return FalseSolution in Python
To implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (BST), we will use a stack to help traverse the tree. The stack will keep track of the nodes to visit next. This ensures that we can efficiently return the next smallest element in the BST.
Python
class BSTIterator:
def __init__(self, root: Optional[TreeNode]):
# Initialize a stack to simulate the in-order traversal
self.stack = []
# Start with the leftmost node
self._leftmost_inorder(root)
def _leftmost_inorder(self, root):
# Push all the leftmost nodes onto the stack
while root:
self.stack.append(root)
root = root.left
def next(self) -> int:
# Node at the top of the stack is the next smallest element
topmost_node = self.stack.pop()
# If the node has a right child, we push all the leftmost nodes
# of the right subtree onto the stack
if topmost_node.right:
self._leftmost_inorder(topmost_node.right)
return topmost_node.val
def hasNext(self) -> bool:
# If the stack is not empty, there is a next element
return len(self.stack) > 0Detailed Comments in Code
- Initialization (
__init__method):- We initialize an empty stack to keep track of nodes during the in-order traversal.
- We call the helper method
_leftmost_inorderto push all leftmost nodes starting from the root onto the stack. This ensures that the smallest element is on top of the stack.
- Helper Method (
_leftmost_inordermethod):- This method takes a node and pushes all the leftmost nodes from this node down to the stack. This ensures that the next smallest element is always on top of the stack.
- Next Element (
nextmethod):- We pop the top element from the stack, which is the next smallest element.
- If the popped element has a right child, we push all the leftmost nodes of the right subtree onto the stack. This ensures the stack is prepared for the subsequent calls.
- Check for Next Element (
hasNextmethod):- We simply check if the stack is non-empty. If it is, there are still elements to be visited.
This implementation ensures that both next and hasNext operations run in average O(1) time, and the space complexity is O(h) where h is the height of the tree. This is because, at most, the stack will contain all the nodes along a path from the root to the leftmost leaf.
Solution in Javascript
JavaScript
/**
* @param {TreeNode} root
*/
var BSTIterator = function(root) {
// Initialize a stack to simulate the in-order traversal
this.stack = [];
// Start with the leftmost node
this._leftmostInorder(root);
};
/**
* @param {TreeNode} root
*/
BSTIterator.prototype._leftmostInorder = function(root) {
// Push all the leftmost nodes onto the stack
while (root !== null) {
this.stack.push(root);
root = root.left;
}
};
/**
* @return {number}
*/
BSTIterator.prototype.next = function() {
// Node at the top of the stack is the next smallest element
let topmostNode = this.stack.pop();
// If the node has a right child, we push all the leftmost nodes
// of the right subtree onto the stack
if (topmostNode.right !== null) {
this._leftmostInorder(topmostNode.right);
}
return topmostNode.val;
};
/**
* @return {boolean}
*/
BSTIterator.prototype.hasNext = function() {
// If the stack is not empty, there is a next element
return this.stack.length > 0;
};Solution in Java
Java
import java.util.Stack;
class BSTIterator {
private Stack<TreeNode> stack;
public BSTIterator(TreeNode root) {
// Initialize the stack to simulate the in-order traversal
stack = new Stack<>();
// Start with the leftmost node
_leftmostInorder(root);
}
private void _leftmostInorder(TreeNode root) {
// Push all the leftmost nodes onto the stack
while (root != null) {
stack.push(root);
root = root.left;
}
}
public int next() {
// Node at the top of the stack is the next smallest element
TreeNode topmostNode = stack.pop();
// If the node has a right child, we push all the leftmost nodes
// of the right subtree onto the stack
if (topmostNode.right != null) {
_leftmostInorder(topmostNode.right);
}
return topmostNode.val;
}
public boolean hasNext() {
// If the stack is not empty, there is a next element
return !stack.isEmpty();
}
}Solution in C#
C#
using System.Collections.Generic;
public class BSTIterator {
private Stack<TreeNode> stack;
public BSTIterator(TreeNode root) {
// Initialize the stack to simulate the in-order traversal
stack = new Stack<TreeNode>();
// Start with the leftmost node
LeftmostInorder(root);
}
private void LeftmostInorder(TreeNode root) {
// Push all the leftmost nodes onto the stack
while (root != null) {
stack.Push(root);
root = root.left;
}
}
public int Next() {
// Node at the top of the stack is the next smallest element
TreeNode topmostNode = stack.Pop();
// If the node has a right child, we push all the leftmost nodes
// of the right subtree onto the stack
if (topmostNode.right != null) {
LeftmostInorder(topmostNode.right);
}
return topmostNode.val;
}
public bool HasNext() {
// If the stack is not empty, there is a next element
return stack.Count > 0;
}
}