Binary Search Tree Iterator
Problem Description
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 theBSTIteratorclass. Therootof 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()Returnstrueif there exists a number in the traversal to the right of the pointer, otherwise returnsfalse.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
Constraints:
- The number of nodes in the tree is in the range [1, 105].
- 0 <= Node.val <= 106
- At most 105 calls will be made to
hasNext, andnext.
Follow up:
- Could you implement
next()andhasNext()to run in averageO(1)time and useO(h)memory, wherehis the height of the tree?
Solve it on LeetCode
Approaches
1. Basic Approach: In-Order Traversal with List
Intuition:
The basic intuition is to leverage the property of a BST where an in-order traversal gives nodes in a non-decreasing order. We can perform an in-order traversal of the tree, store all nodes in a list, and then use this list to ensure constant time access to the next smallest node.
Approach:
- Perform an in-order traversal of the BST.
- Store the elements in a list as they are visited.
- Use an index to track the current element in the list.
next()simply retrieves the element at the current index and then increments it.hasNext()checks if the current index is less than the list size.
Code:
- Time Complexity:
Constructor: O(N), where N is the number of nodes in the tree, due to the in-order traversal.next(): O(1).hasNext(): O(1).- Space Complexity: O(N), required for storing the in-order traversal.
2. Optimal Approach: Controlled Recursion
Intuition:
The goal is to simulate the in-order traversal using controlled stack-based recursion. The benefit is an iterative approach with a controlled stack of nodes which represents the path from the root to the next smallest node. Thus, it uses less memory than storing all nodes.
Approach:
- Use the stack to keep track of the nodes that need to be visited.
- Initialize by traversing from the root to the leftmost node, pushing all the nodes on the path to the stack.
hasNext()is simple: check if there are any nodes left in the stack.- For
next(), pop the top node from the stack (the current smallest). - If this node has a right child, push all its left descendants onto the stack.
Code:
- Time Complexity:
Constructor: O(H), where H is the height of the tree, due to pushing nodes from the root to the leftmost leaf.next(): Amortized O(1), each node pushed or popped exactly once.hasNext(): O(1).- Space Complexity: O(H), where H is the height of the tree, for the stack. This is optimal for very skewed trees.