Medium
Quiz
#173 Binary Search Tree Iterator
APPROACH
Implement the BSTIterator class that represents a cursor advancing through the in-order traversal of a binary search tree (BST):
- BSTIterator(TreeNode root) initializes the iterator. The cursor starts before the smallest element in the BST.
- boolean hasNext() returns true if a next element exists in the traversal.
- int next() advances the cursor and returns the next smallest value.
The first call to next() returns the smallest element in the BST.
You may assume that next() calls will always be valid.
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]
Example 2:
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
1 of 4
1:00
What is the optimal approach for this problem?