Binary Search Tree Iterator
Implement an iterator over a Binary Search Tree (BST).
The iterator should return the elements in ascending order.
It should support two operations:
next()
Returns the next smallest element in the BST.
hasNext()
Returns true if there are more elements remaining.
Example:
7
/ \
3 15
/ \
9 20
Inorder traversal:
3 → 7 → 9 → 15 → 20
So the iterator should return:
3
7
9
15
20
Example 1
Input
root = [7,3,15,null,null,9,20]
Output
3 7 9 15 20
Explanation
The tree is:
7
/ \
3 15
/ \
9 20
The inorder traversal is:
3 → 7 → 9 → 15 → 20
Therefore, repeated calls to next() return:
next() → 3
next() → 7
next() → 9
next() → 15
next() → 20
After returning 20:
hasNext() → false
Example 2
Input
root = [3,1,5]
Output
1 3 5
Explanation
The tree is:
3
/ \
1 5
Its inorder traversal is:
1 → 3 → 5
So the iterator returns the elements in exactly this order.
Constraints
Hints:
Hint 1
An inorder traversal of a BST gives values in ascending order.
Hint 2
You don't need to store the entire traversal.
Use a stack to simulate inorder traversal.
Author & Technical Reviewer
Technically reviewed by: ExamAdda Technical Review Team
Technical Reviewers, ExamAdda
Software engineers at ExamAdda who check every article's definitions, complexity claims and code examples before and after publishing.
Published
Aug 15, 2026
Last updated
Aug 16, 2026
Content Verification Methodology
Definitions and complexity claims were checked against authoritative computer-science references. Code examples were compiled and tested with standard, boundary and edge-case inputs.
Expected Output