Problem Description

You need to implement a BSTIterator class that allows you to iterate through a Binary Search Tree (BST) in in-order traversal sequence (left → root → right).

The class should have three main components:

1. Constructor BSTIterator(TreeNode root): Takes the root of a BST and initializes the iterator. The internal pointer should start at a position before the smallest element (conceptually at a "non-existent" position smaller than any element in the tree).

2. Method next(): Returns the next smallest number in the BST and advances the pointer. Since the pointer starts before the first element, the first call to next() will return the smallest element in the BST.

3. Method hasNext(): Returns true if there are more elements to iterate through (elements to the right of the current pointer position), and false otherwise.

The key requirements are:

• The iteration should follow in-order traversal order, which for a BST means visiting nodes in ascending order of their values
• You can assume that next() will only be called when there are remaining elements (when hasNext() returns true)
• The iterator should efficiently traverse through all nodes exactly once

Example usage pattern:

obj = BSTIterator(root)
while obj.hasNext():
    value = obj.next()  # Gets next value in ascending order

The solution shown uses a preprocessing approach where it performs a complete in-order traversal during initialization to store all values in a list self.vals. It then uses a cursor self.cur to track the current position in this list. The next() method returns the value at the current cursor position and increments it, while hasNext() checks if the cursor has reached the end of the list.

Intuition

When we need to iterate through a BST in ascending order, we're essentially asking for an in-order traversal. The natural question is: how can we provide elements one at a time on demand, rather than all at once?

The most straightforward approach is to perform the complete in-order traversal upfront and store all values in a list. This way, we transform the tree traversal problem into a simple array iteration problem. Think of it like reading a book - instead of searching through scattered pages each time, we arrange all pages in order first, then simply flip through them one by one.

Why does this work well? In-order traversal of a BST naturally gives us elements in sorted (ascending) order. By collecting all values during initialization:

• We do the complex tree navigation work once
• The next() operation becomes a simple array access with O(1) time
• The hasNext() check is just comparing indices with O(1) time

The trade-off here is space - we're using O(n) extra space to store all node values. However, this makes the iterator operations extremely simple and efficient. We maintain a cursor (self.cur) that starts at 0 and moves forward with each next() call, mimicking how we'd iterate through a regular list.

This approach is like preparing a playlist before a party - you spend time upfront organizing the songs in order, but then playing the next song is instant. The alternative would be searching through your music library each time you need the next song, which would be more complex and potentially slower for each operation.

Solution Approach

The solution uses a preprocessing strategy with in-order traversal to collect all BST values during initialization. Here's the step-by-step implementation:

1. Initialization Phase (__init__ method)

The constructor sets up three key components:

• self.cur = 0: A cursor to track our current position in the traversal
• self.vals = []: A list to store all BST values in sorted order
• A nested inorder function that performs recursive in-order traversal

The inorder function follows the classic recursive pattern:

def inorder(root):
    if root:
        inorder(root.left)    # Visit left subtree
        self.vals.append(root.val)  # Process current node
        inorder(root.right)   # Visit right subtree

This traversal visits nodes in the exact order we need: left → root → right, which for a BST means ascending order. After initialization, self.vals contains all values sorted from smallest to largest.

2. Next Element Retrieval (next method)

This method is straightforward:

def next(self) -> int:
    res = self.vals[self.cur]  # Get value at current position
    self.cur += 1              # Move cursor forward
    return res

Since we've already arranged values in order, getting the next element is just array indexing at position self.cur, then incrementing the cursor for the next call.

3. Checking for More Elements (hasNext method)

The check is a simple boundary condition:

def hasNext(self) -> bool:
    return self.cur < len(self.vals)

If the cursor hasn't reached the end of our values list, there are more elements to iterate through.

Time and Space Complexity

• Initialization: O(n) time to traverse all n nodes, O(n) space for the recursion stack and storing values
• next(): O(1) time - simple array access
• hasNext(): O(1) time - simple comparison

The total space complexity is O(n) for storing all node values, which trades memory for the simplicity and speed of iterator operations.

Example Walkthrough

Let's walk through the solution with a small BST example:

       4
      / \
     2   6
    / \   \
   1   3   7

Step 1: Initialization When we create BSTIterator(root), the constructor:

• Sets self.cur = 0 (cursor at start position)
• Creates empty list self.vals = []
• Performs in-order traversal:
  • Visit node 1: vals = [1]
  • Visit node 2: vals = [1, 2]
  • Visit node 3: vals = [1, 2, 3]
  • Visit node 4: vals = [1, 2, 3, 4]
  • Visit node 6: vals = [1, 2, 3, 4, 6]
  • Visit node 7: vals = [1, 2, 3, 4, 6, 7]

After initialization:

• self.vals = [1, 2, 3, 4, 6, 7] (all values in ascending order)
• self.cur = 0 (pointing to index 0)

Step 2: First hasNext() call

• Check: cur (0) < len(vals) (6) → Returns true

Step 3: First next() call

• Get vals[0] = 1
• Increment cursor: cur = 1
• Return 1

Step 4: Second next() call

• Get vals[1] = 2
• Increment cursor: cur = 2
• Return 2

Step 5: Continue iterating...

• next() returns 3, cursor becomes 3
• next() returns 4, cursor becomes 4
• next() returns 6, cursor becomes 5
• next() returns 7, cursor becomes 6

Step 6: Final hasNext() call

• Check: cur (6) < len(vals) (6) → Returns false
• No more elements to iterate!

The iterator successfully returned all BST values in ascending order: 1, 2, 3, 4, 6, 7.

Solution Implementation

Time and Space Complexity

Time Complexity:

• __init__: O(n) where n is the number of nodes in the BST. The inorder traversal visits each node exactly once to build the values array.
• next(): O(1) as it simply accesses an element from the array by index and increments the cursor.
• hasNext(): O(1) as it only performs a simple comparison between the cursor and array length.

Space Complexity:

• Overall: O(n) where n is the number of nodes in the BST.
  • The self.vals array stores all n values from the tree.
  • The recursive inorder traversal uses O(h) space for the call stack, where h is the height of the tree. In the worst case (skewed tree), h = n, and in the best case (balanced tree), h = log(n).
  • Since we're storing all values in the array, the dominant space complexity is O(n).

Note: This implementation trades space for simplicity by pre-computing all values during initialization. An alternative approach using a stack could achieve O(h) average space complexity by computing values on-demand during iteration.

Common Pitfalls

1. Memory Inefficiency for Large Trees

The preprocessing approach stores all n values upfront, which can be problematic for very large BSTs where memory is constrained. If the BST contains millions of nodes but you only need to iterate through a few elements, you're wasting significant memory.

Solution: Use a lazy evaluation approach with a stack to store only the path to the current node:

class BSTIterator:
    def __init__(self, root: TreeNode):
        self.stack = []
        self._push_all_left(root)
  
    def _push_all_left(self, node):
        while node:
            self.stack.append(node)
            node = node.left
  
    def next(self) -> int:
        node = self.stack.pop()
        if node.right:
            self._push_all_left(node.right)
        return node.val
  
    def hasNext(self) -> bool:
        return len(self.stack) > 0

This approach uses O(h) space where h is the height of the tree, instead of O(n).

2. Handling Empty Trees

The current solution works correctly for empty trees (when root is None), but developers might forget to test this edge case or might add unnecessary null checks.

What to verify:

• Empty tree should result in hasNext() returning False immediately
• The values list remains empty, so the cursor logic still works

3. Thread Safety Issues

If multiple threads try to use the same iterator instance concurrently, the shared current_index variable can lead to race conditions where:

• Two threads might get the same value from next()
• The index might skip values or go out of bounds

Solution: Either:

• Document that the iterator is not thread-safe
• Add synchronization locks around state modifications
• Create separate iterator instances for each thread

4. Incorrect Assumption About BST Properties

Developers might assume the BST is balanced or has specific properties. The solution works for any valid BST structure (balanced or unbalanced), but performance characteristics differ:

• Balanced BST: Stack approach uses O(log n) space
• Skewed BST: Stack approach uses O(n) space in worst case

Always consider worst-case scenarios when analyzing complexity.