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.boolean hasPrev() Returns true if there exists a number in the traversal to the left of the pointer, otherwise returns false.int prev() Moves the pointer to the left, 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() and prev() calls will always be valid. That is, there will be at least a next/previous number in the in-order traversal when next()/prev() is called.
Example 1:
Input ["BSTIterator", "next", "next", "prev", "next", "hasNext", "next", "next", "next", "hasNext", "hasPrev", "prev", "prev"] [[[7, 3, 15, null, null, 9, 20]], [null], [null], [null], [null], [null], [null], [null], [null], [null], [null], [null], [null]] Output [null, 3, 7, 3, 7, true, 9, 15, 20, false, true, 15, 9] Explanation // The underlined element is where the pointer currently is. BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]); // state is [3, 7, 9, 15, 20] bSTIterator.next(); // state becomes [3, 7, 9, 15, 20], return 3 bSTIterator.next(); // state becomes [3, 7, 9, 15, 20], return 7 bSTIterator.prev(); // state becomes [3, 7, 9, 15, 20], return 3 bSTIterator.next(); // state becomes [3, 7, 9, 15, 20], return 7 bSTIterator.hasNext(); // return true bSTIterator.next(); // state becomes [3, 7, 9, 15, 20], return 9 bSTIterator.next(); // state becomes [3, 7, 9, 15, 20], return 15 bSTIterator.next(); // state becomes [3, 7, 9, 15, 20], return 20 bSTIterator.hasNext(); // return false bSTIterator.hasPrev(); // return true bSTIterator.prev(); // state becomes [3, 7, 9, 15, 20], return 15 bSTIterator.prev(); // state becomes [3, 7, 9, 15, 20], return 9
Constraints:
[1, 105].0 <= Node.val <= 106105 calls will be made to hasNext, next, hasPrev, and prev.Follow up: Could you solve the problem without precalculating the values of the tree?
Problem Overview: Design an iterator for a Binary Search Tree (BST) that supports both forward and backward traversal. Besides the usual next() and hasNext(), the iterator must also implement prev() and hasPrev(), allowing you to move one step back in the in-order traversal sequence.
Approach 1: In-order Traversal + Array (O(n) time, O(n) space)
The simplest approach is to flatten the BST using an in-order traversal and store the result in an array. Since in-order traversal of a Binary Search Tree produces sorted values, the iterator becomes a simple index moving forward or backward through that array. Build the array once during initialization with a DFS traversal of the binary tree. Maintain an index pointer that moves right for next() and left for prev().
This approach makes every iterator operation constant time because it only updates an index. The trade-off is memory usage: you store all n nodes upfront. This solution is straightforward, easy to implement, and performs well when the tree size is manageable.
Approach 2: Lazy In-order Traversal with Stack + History (O(1) amortized time, O(h + k) space)
A more memory-efficient design performs in-order traversal lazily using a stack. The stack stores the traversal state, pushing left children until the smallest node is reached. Each call to next() processes the stack similarly to a standard BST iterator. To support prev(), maintain a list of already visited values and an index pointing to the current position. If the user moves backward, simply decrement the index. If moving forward beyond visited elements, resume traversal from the stack.
This hybrid structure combines a traversal stack with a history list. The stack depth is at most the tree height h, while the history grows to the number of visited nodes k. Each node is pushed and popped at most once, giving amortized O(1) time per operation. Compared with the full-array approach, it avoids computing the entire traversal upfront.
Recommended for interviews: The lazy traversal with a stack and history list demonstrates stronger understanding of iterator design and tree traversal. The array approach is perfectly valid and quick to implement, but interviewers often prefer the stack-based iterator because it processes nodes on demand and mirrors real iterator patterns used in system design.
We can use in-order traversal to store the values of all nodes in the binary search tree into an array nums, and then use the array to implement the iterator. We define a pointer i, initially i = -1, which points to an element in the array nums. Each time we call next(), we add 1 to the value of i and return nums[i]; each time we call prev(), we subtract 1 from the value of i and return nums[i].
In terms of time complexity, initializing the iterator requires O(n) time, where n is the number of nodes in the binary search tree. Each call to next() and prev() requires O(1) time. In terms of space complexity, we need O(n) space to store the values of all nodes in the binary search tree.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| In-order Traversal + Array | O(n) preprocessing, O(1) per operation | O(n) | Best when simplicity matters and memory for storing all nodes is acceptable |
| Lazy In-order Traversal with Stack + History | O(1) amortized per operation | O(h + k) | Preferred for interview discussions and when avoiding full traversal upfront |
1586. Binary Search Tree Iterator II (Leetcode Medium) • Programming Live with Larry • 331 views views
Watch 1 more video solutions →Practice Binary Search Tree Iterator II with our built-in code editor and test cases.
Practice on FleetCode