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 the BSTIterator class. The root of 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() Returns true if there exists a number in the traversal to the right of the pointer, otherwise returns false.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.
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 False
Constraints:
[1, 105].0 <= Node.val <= 106105 calls will be made to hasNext, and next.Follow up:
next() and hasNext() to run in average O(1) time and use O(h) memory, where h is the height of the tree?The key idea for solving Binary Search Tree Iterator is to simulate an inorder traversal of a BST, since inorder traversal naturally returns values in sorted order. Instead of traversing the entire tree at once, the iterator should return the next smallest element on demand.
A common approach uses a stack to maintain traversal state. During initialization, push all the left children of the root onto the stack. The top of the stack always represents the next smallest element. When next() is called, pop the top node and process it. If that node has a right child, push that child and all of its left descendants onto the stack.
This design ensures that each node is processed only once while maintaining the correct order. The next() operation runs in amortized O(1) time, while the stack stores at most the height of the tree.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Stack-based Inorder Iterator | Initialization: O(h), next(): O(1) amortized | O(h) |
take U forward
This approach involves using a stack to simulate the in-order traversal of a binary search tree (BST). The stack is used to keep track of nodes to visit next, starting from the leftmost node (the smallest element). Each time next() is called, the stack pops one node, processes it, and then adds right child nodes to the stack to maintain the in-order sequence. This approach takes advantage of the tree's properties to efficiently traverse it.
Time Complexity: The average time complexity is O(1) for next() and hasNext() methods, though next() can take up to O(h) time in the worst case, where h is the height of the tree.
Space Complexity: O(h) due to the depth of the stack, where h is the height of the tree.
1class BSTIterator:
2 def __init__(self, root: TreeNode):
3 self.stack = []
4 self._push_left_nodes
The Python solution uses a list to simulate the stack. The iterator's constructor pushes all left children of the root into the stack. next() gives the next smallest number by popping the stack and potentially adding a right child’s children if they exist. hasNext() checks if the stack is empty to determine the presence of further elements.
Morris Traversal is an in-order tree traversal technique that doesn't require stack or recursion, thus using O(1) auxiliary space. It temporarily modifies the tree structure to maintain caching pointers, ensuring nodes are revisited as necessary. Once traversal completes, the tree reverts to its original form.
Time Complexity: O(1) on average, with O(n) total time for n nodes.
Space Complexity: O(1) without recourse to stack/recursion.
private TreeNode current;
public BSTIterator(TreeNode root) {
current = root;
}
public bool HasNext() {
return current != null;
}
public int Next() {
int result = 0;
while (current != null) {
if (current.left == null) {
result = current.val;
current = current.right;
break;
} else {
TreeNode pred = FindPredecessor(current);
if (pred.right == null) {
pred.right = current;
current = current.left;
} else {
pred.right = null;
result = current.val;
current = current.right;
break;
}
}
}
return result;
}
private TreeNode FindPredecessor(TreeNode node) {
TreeNode pred = node.left;
while (pred.right != null && pred.right != node) {
pred = pred.right;
}
return pred;
}
}
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem or similar iterator design questions frequently appear in FAANG-style interviews. It tests understanding of BST properties, stack usage, and lazy traversal design.
The optimal approach uses a stack to simulate an inorder traversal of the BST. By pushing all left descendants initially and updating the stack whenever a node with a right child is processed, the iterator can return the next smallest value efficiently. This keeps next() operations amortized O(1).
In a binary search tree, inorder traversal visits nodes in ascending sorted order. Since the iterator must return elements from smallest to largest, inorder traversal naturally satisfies this requirement.
A stack is the most effective data structure for this problem. It helps maintain the traversal state and ensures that the next smallest element is always available at the top. This mirrors the behavior of a controlled inorder traversal.
C# employs the Morris traversal approach to realize space-efficient in-order visits. The implementation dynamically modifies tree connections for orderly node retrieval, restoring them post-traversal. `HasNext` maintains awareness of the process’s continuation state.