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?Problem Overview: Design an iterator over a Binary Search Tree (BST) that returns nodes in ascending order. The iterator must support next() and hasNext() while maintaining the BST’s in-order traversal sequence.
Approach 1: Using Stack for Controlled In-order Traversal (Time: O(n) total, O(1) amortized per operation, Space: O(h))
This approach simulates the recursive in-order traversal of a binary tree using an explicit stack. The key idea is to preload the stack with the entire left spine of the tree during initialization. The top of the stack always represents the next smallest node. When next() is called, you pop the top node and then push the left spine of its right child. This ensures the stack always holds the next valid candidates in sorted order.
The iterator never processes more nodes than necessary. Each node is pushed and popped exactly once, so the total traversal work is O(n), which makes each next() call amortized O(1). Space usage depends on the height of the tree, typically O(h). This method fits naturally with how binary search trees produce sorted output through in-order traversal and is the most common implementation in production and interviews.
Approach 2: Morris In-order Traversal (Time: O(n), Space: O(1))
Morris traversal removes the need for an auxiliary stack by temporarily modifying the tree structure. For each node, you locate its inorder predecessor and create a temporary threaded link back to the current node. This allows traversal to return after finishing the left subtree without recursion or a stack. When the traversal revisits the predecessor, the temporary link is removed and the algorithm proceeds to the right subtree.
This technique achieves O(1) extra space because it stores traversal state directly in the tree using temporary pointers. Each edge is visited at most twice, keeping the total runtime O(n). However, the tree structure is modified during traversal, which can be undesirable in systems where the tree must remain immutable. Because of this tradeoff, Morris traversal is less common for iterator implementations despite its optimal space usage.
Recommended for interviews: The stack-based controlled in-order traversal is the expected solution. It demonstrates understanding of BST ordering and how to convert recursive traversal into an iterative design using a stack. Morris traversal is a strong follow-up discussion when the interviewer asks how to reduce space from O(h) to O(1), but the stack approach is cleaner and easier to implement correctly under interview constraints.
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.
The C solution for the BSTIterator uses a stack implemented as a linked list with basic stack operations like push and pop. The constructor initializes the stack with all left children of the root node. The `next` function pops the top of the stack, processes the node, and pushes any right child nodes' left children. The `hasNext` function checks if there are elements in the stack, indicating if another call to `next` is valid.
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.
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.
The C solution utilizes Morris traversal to achieve an in-order sequence without extra space. The iterator temporarily modifies the tree with connections called threads to track nodes. As the `next` method works through the tree, each accessed node prints its value and advances by fixing connections afterward. The `hasNext` method merely checks if the tree traversal has completed.
Time Complexity: O(1) on average, with O(n) total time for n nodes.
Space Complexity: O(1) without recourse to stack/recursion.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| Approach | Complexity |
|---|---|
| Approach 1: Using Stack for Controlled In-order Traversal | Time Complexity: The average time complexity is |
| Approach 2: Morris In-order Traversal | Time Complexity: |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Stack-based Controlled In-order Traversal | O(n) total, O(1) amortized per next() | O(h) | Standard iterator implementation; clean design for interviews and production |
| Morris In-order Traversal | O(n) | O(1) | When minimizing auxiliary space and temporary tree modification is acceptable |
L50. Binary Search Tree Iterator | BST | O(H) Space • take U forward • 244,037 views views
Watch 9 more video solutions →Practice Binary Search Tree Iterator with our built-in code editor and test cases.
Practice on FleetCode