Solution Explanation: Binary Search Tree Iterator II

This problem requires implementing a bidirectional iterator for a Binary Search Tree (BST). The iterator should traverse the BST in in-order fashion, allowing movement to the next and previous nodes efficiently.

Approach: In-order Traversal and Array Storage

The most straightforward approach leverages the properties of in-order traversal in BSTs. In-order traversal visits nodes in ascending order. We can perform an initial in-order traversal to collect all node values into an array. This array then serves as the underlying data structure for the iterator. The iterator maintains an index (i) to track the current position within the array.

Algorithm:

1. Constructor (BSTIterator):

   • Performs a recursive in-order traversal of the BST.
   • Stores the values encountered during the traversal in an array (nums).
   • Initializes the index i to -1 (pointing to a position before the first element).

2. hasNext():

   • Checks if the current index i is less than the array's size minus 1. Returns true if there's a next element, false otherwise.

3. next():

   • Increments the index i.
   • Returns the value at nums[i].

4. hasPrev():

   • Checks if the current index i is greater than 0. Returns true if there's a previous element, false otherwise.

5. prev():

   • Decrements the index i.
   • Returns the value at nums[i].

Time and Space Complexity Analysis

• Time Complexity:

  • Constructor: O(N), where N is the number of nodes in the BST, due to the in-order traversal.
  • hasNext(), hasPrev(), next(), prev(): O(1). These operations involve only constant-time array access and index manipulation.

• Space Complexity:

  • O(N) to store the array nums containing all node values. This is the dominant space usage.

Code Implementation (Python)

class BSTIterator:
    def __init__(self, root: Optional[TreeNode]):
        self.nums = []
        def inorder(node):
            if node:
                inorder(node.left)
                self.nums.append(node.val)
                inorder(node.right)
        inorder(root)
        self.i = -1
 
    def hasNext(self) -> bool:
        return self.i < len(self.nums) - 1
 
    def next(self) -> int:
        self.i += 1
        return self.nums[self.i]
 
    def hasPrev(self) -> bool:
        return self.i > 0
 
    def prev(self) -> int:
        self.i -= 1
        return self.nums[self.i]

The implementations in other languages (Java, C++, Go, TypeScript) follow the same logic, adapting the syntax and data structures accordingly. Refer to the provided code snippets in the original response for detailed examples in those languages. The core algorithm and complexity remain consistent across all implementations.