Problem Description

You need to implement a BSTIterator class that acts as an iterator for traversing a Binary Search Tree (BST) in in-order fashion. The iterator should support moving both forward and backward through the tree's values.

The class should have the following methods:

1. BSTIterator(TreeNode root): Constructor that takes the root of a BST. The iterator's pointer should start at a position before the smallest element (conceptually at position -1).

2. hasNext(): Returns true if there's at least one more element to the right of the current pointer position in the in-order traversal sequence, otherwise returns false.

3. next(): Moves the pointer one position to the right and returns the value at the new position. This method assumes there's always a valid next element when called.

4. hasPrev(): Returns true if there's at least one element to the left of the current pointer position in the in-order traversal sequence, otherwise returns false.

5. prev(): Moves the pointer one position to the left and returns the value at the new position. This method assumes there's always a valid previous element when called.

Key points to understand:

• In-order traversal of a BST visits nodes in ascending order (left subtree → root → right subtree)
• The pointer starts before the first element, so the first call to next() returns the smallest value
• The iterator needs to support bidirectional movement through the sorted sequence
• You can assume next() and prev() will only be called when valid (when hasNext() or hasPrev() return true respectively)

The solution approach stores all BST values in an array using in-order traversal during initialization. It then uses an index pointer i (starting at -1) to track the current position. Moving forward increments i and moving backward decrements i, with the corresponding array value being returned.

Intuition

When we need to iterate through a BST in sorted order while supporting both forward and backward movement, the key insight is that in-order traversal naturally gives us the elements in ascending order.

Think about what happens during in-order traversal: we visit the left subtree first, then the current node, then the right subtree. For a BST, this means we get all values in sorted order. Once we have this sorted sequence, moving forward and backward becomes straightforward - it's just like navigating through an array with an index.

The challenge is supporting bidirectional movement. If we only needed to move forward, we could use a stack-based approach to traverse nodes on-the-fly. But since we also need to move backward (with the prev() method), keeping track of previously visited nodes becomes necessary.

The simplest approach is to perform a complete in-order traversal during initialization and store all values in an array nums. This gives us:

• O(1) time complexity for all iterator operations (hasNext(), next(), hasPrev(), prev())
• Easy bidirectional movement using a simple index pointer i
• Clear implementation where i tracks our current position in the sorted sequence

We initialize i = -1 to represent a position "before" the first element. This ensures that the first call to next() moves to index 0 and returns the smallest element, matching the problem's requirement. From there:

• next() increments i and returns nums[i]
• prev() decrements i and returns nums[i]
• hasNext() checks if i < len(nums) - 1
• hasPrev() checks if i > 0

This trade-off of using O(n) space for storing all values upfront gives us the simplicity and efficiency needed for constant-time bidirectional iteration.

Learn more about Stack, Tree, Binary Search Tree and Binary Tree patterns.

Solution Approach

The implementation uses in-order traversal combined with an array-based storage approach to create a bidirectional iterator for the BST.

Data Structures Used:

• Array (self.nums): Stores all BST values in sorted order
• Index pointer (self.i): Tracks the current position in the array

Implementation Steps:

1. Initialization (__init__ method):

   • Create an empty array self.nums to store all node values
   • Define a recursive DFS helper function for in-order traversal:

     def dfs(root):
         if root is None:
             return
         dfs(root.left)      # Visit left subtree
         self.nums.append(root.val)  # Process current node
         dfs(root.right)     # Visit right subtree

   • Call dfs(root) to populate the array with all values in sorted order
   • Initialize the pointer self.i = -1 to position it before the first element

2. hasNext() method:

   • Check if there are more elements to the right: self.i < len(self.nums) - 1
   • Returns True if the current index is less than the last valid index

3. next() method:

   • Increment the pointer: self.i += 1
   • Return the value at the new position: return self.nums[self.i]

4. hasPrev() method:

   • Check if there are elements to the left: self.i > 0
   • Returns True only if moving back won't go before the first element

5. prev() method:

   • Decrement the pointer: self.i -= 1
   • Return the value at the new position: return self.nums[self.i]

Time and Space Complexity:

• Initialization: O(n) time for traversing all n nodes, O(n) space for storing values
• All iterator operations: O(1) time since we're just accessing array elements and updating an index
• Overall space: O(n) for storing the complete sorted sequence

The beauty of this solution lies in its simplicity - by pre-computing the in-order traversal, we transform the tree navigation problem into simple array indexing, making bidirectional iteration trivial to implement.

Example Walkthrough

Let's walk through how the BSTIterator works with a small BST:

       4
      / \
     2   6
    / \   \
   1   3   7

Step 1: Initialization When we create BSTIterator(root), the in-order traversal runs:

• Visit left subtree of 4 → goes to 2
• Visit left subtree of 2 → goes to 1
• Visit 1 (leaf) → add 1 to array
• Back to 2 → add 2 to array
• Visit right subtree of 2 → goes to 3
• Visit 3 (leaf) → add 3 to array
• Back to 4 → add 4 to array
• Visit right subtree of 4 → goes to 6
• Visit 6 → add 6 to array
• Visit right subtree of 6 → goes to 7
• Visit 7 (leaf) → add 7 to array

Result: nums = [1, 2, 3, 4, 6, 7], i = -1

Step 2: First operations

hasNext()  # i=-1, len(nums)=6, returns True (since -1 < 5)
next()     # i becomes 0, returns nums[0] = 1

State: i = 0, pointing at value 1

Step 3: Moving forward

next()     # i becomes 1, returns nums[1] = 2
next()     # i becomes 2, returns nums[2] = 3

State: i = 2, pointing at value 3

Step 4: Checking boundaries

hasPrev()  # i=2, returns True (since 2 > 0)
hasNext()  # i=2, returns True (since 2 < 5)

Step 5: Moving backward

prev()     # i becomes 1, returns nums[1] = 2
prev()     # i becomes 0, returns nums[0] = 1
hasPrev()  # i=0, returns False (since 0 is not > 0)

Step 6: Moving to the end

next()     # i becomes 1, returns 2
next()     # i becomes 2, returns 3
next()     # i becomes 3, returns 4
next()     # i becomes 4, returns 6
next()     # i becomes 5, returns 7
hasNext()  # i=5, returns False (since 5 is not < 5)

The iterator successfully navigates bidirectionally through the BST values in sorted order, with the pointer tracking our position in the pre-computed array.

Solution Implementation

Time and Space Complexity

Time Complexity:

• Initialization (__init__): O(n) where n is the number of nodes in the binary search tree. The constructor performs an in-order traversal using DFS to visit every node exactly once and store its value in the nums list.
• hasNext() method: O(1) - Simply compares the current index with the length of the array.
• next() method: O(1) - Increments the index and returns the value at that position in the array.
• hasPrev() method: O(1) - Simply checks if the current index is greater than 0.
• prev() method: O(1) - Decrements the index and returns the value at that position in the array.

Space Complexity:

• O(n) where n is the number of nodes in the binary search tree. The nums list stores all node values from the BST after the in-order traversal. Additionally, the recursive DFS call stack can go up to O(h) depth where h is the height of the tree, but since we're already using O(n) space for the array, the overall space complexity remains O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Initial Pointer Position

A common mistake is initializing the pointer at index 0 instead of -1. This would cause the first next() call to skip the smallest element.

Wrong Implementation:

def __init__(self, root):
    self.values = []
    # ... perform traversal ...
    self.current_index = 0  # WRONG: Starting at first element

Why it's wrong: The problem states the pointer should start "before the smallest element". If we start at 0, the first next() call would move to index 1, returning the second smallest value instead of the smallest.

Correct Implementation:

def __init__(self, root):
    self.values = []
    # ... perform traversal ...
    self.current_index = -1  # CORRECT: Starting before first element

2. Off-by-One Errors in Boundary Checks

Another frequent error occurs in the hasPrev() and hasNext() methods with incorrect boundary conditions.

Wrong Implementation:

def hasNext(self):
    return self.current_index < len(self.values)  # WRONG: allows going past last element

def hasPrev(self):
    return self.current_index >= 0  # WRONG: allows going before first element when at index 0

Why it's wrong:

• For hasNext(): When at the last element (index len-1), this would incorrectly return True
• For hasPrev(): When at index 0 (first element), we shouldn't be able to go back further

Correct Implementation:

def hasNext(self):
    return self.current_index < len(self.values) - 1  # Can move forward if not at last element

def hasPrev(self):
    return self.current_index > 0  # Can move backward only if past the first element

3. Memory Optimization Misconception

Some might try to optimize memory by not storing all values upfront, instead traversing the tree on each operation. While this saves space, it violates the O(1) time complexity requirement for iterator operations.

Inefficient Alternative:

def next(self):
    # Trying to find next element by traversing tree each time
    # This would be O(h) or O(n) time complexity, not O(1)
    current = self.find_current_node()
    successor = self.find_inorder_successor(current)
    return successor.val

Why the array approach is better: Although it uses O(n) space, it guarantees O(1) time for all iterator operations, which is typically the expected behavior for iterators.

4. Not Handling Empty Trees

Forgetting to handle the edge case where the BST is empty (root is None).

Potential Issue:

def hasNext(self):
    # This works fine even for empty trees since len([]) - 1 = -1
    # and -1 < -1 is False
    return self.current_index < len(self.values) - 1

While the current implementation handles empty trees correctly (empty array means hasNext() and hasPrev() always return False), it's good practice to be aware of this edge case and ensure your implementation handles it properly.