Binary Search Tree Iterator II

Problem Statement

The BSTIterator class is designed to provide a controlled way of iterating through a binary search tree (BST) using its in-order traversal. The features of the class include:

• Initialization of the iterator with the root of the BST.
• Moving the internal pointer to simulate steps through the traversal, both forward and backwards.
• Checking the availability of next and previous nodes relative to the current position of the pointer.

Key functionalities:

1. Initialization (BSTIterator(TreeNode root)): Constructs an instance with the given tree's root. Internally, it might store the elements in a way that supports efficient in-order traversal from the smallest to largest element.
2. Check Next (boolean hasNext()): Determines if there are nodes ahead in the traversal sequence, returning true or false.
3. Next Element (int next()): Moves to the next element in the in-order sequence and returns its value.
4. Check Previous (boolean hasPrev()): Checks whether elements are available before the current pointer in the traversal sequence.
5. Previous Element (int prev()): Moves to the previous element in the sequence, returning its value.

The BSTIterator initiates its pointer at a virtual position before the smallest element, ensuring that the first next() invocation will correctly return the smallest element in the tree.

Examples

Example 1

Input:

["BSTIterator", "next", "next", "prev", "next", "hasNext", "next", "next", "next", "hasNext", "hasPrev", "prev", "prev"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], [], [], [], []]

Output:

[null, 3, 7, 3, 7, true, 9, 15, 20, false, true, 15, 9]

Explanation: Let the BST in-order sequence be [3, 7, 9, 15, 20].

1. BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
   Initializes the iterator.

2. bSTIterator.next(); ➜ returns 3

3. bSTIterator.next(); ➜ returns 7

4. bSTIterator.prev(); ➜ returns 3

5. bSTIterator.next(); ➜ returns 7

6. bSTIterator.hasNext(); ➜ returns true

7. bSTIterator.next(); ➜ returns 9

8. bSTIterator.next(); ➜ returns 15

9. bSTIterator.next(); ➜ returns 20

10. bSTIterator.hasNext(); ➜ returns false

11. bSTIterator.hasPrev(); ➜ returns true

12. bSTIterator.prev(); ➜ returns 15

13. bSTIterator.prev(); ➜ returns 9

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, next, hasPrev, and prev.

Approach and Intuition

The problem revolves around simulating an in-order traversal on a BST using an iterator with additional capabilities like checking for next and previous elements and moving the pointer accordingly.

Key Concepts in Play:

• In-order Traversal: This type of traversal ensures that the tree's elements are processed in a strictly increasing order, which aligns perfectly with the sequential access provided by an iterator. The in-order traversal can be typically implemented using recursion or a stack.

Steps to Approach:

1. Initialization:
   • Convert the given tree into a flat structure (like an array or list) representing the in-order traversal. This preprocessing step can be achieved by leveraging a stack where we iteratively push left children, thereby ensuring that we process the smallest element first.
2. hasNext() and next():
   • For hasNext(), simply check whether there are unvisited elements after the current index.
   • For next(), move the internal cursor to the right, and return the value at the new cursor position.
3. hasPrev() and prev():
   • For hasPrev(), verify that the cursor is not at the very start of the in-order traversal.
   • For prev(), move the cursor left, returning the value at the cursor.

Effectiveness of Approach:

• The use of a list or array to store in-order elements converts potentially deep tree traversal to simple index operations on an array, enhancing access times for next() and prev() to constant time, O(1).
• Space complexity becomes O(n) due to the storage of the entire tree's nodes in a sequential structure.
• This direct approach conforms to the maximum constraint of operations, efficiently managing repeated calls to navigation methods.

Given the constraints provided which include very high operation counts (up to 105) but with individual operations bounded by constant time, this approach is effective in providing timely responses to iterator queries.

Solutions

class BSTTraversal {

    Deque<TreeNode> nodeStack;
    List<Integer> values;
    TreeNode currNode;
    int index;

    public BSTTraversal(TreeNode root) {
        currNode = root;
        nodeStack = new ArrayDeque();
        values = new ArrayList();
        index = -1;
    }
    
    public boolean hasNext() {
        return !nodeStack.isEmpty() || currNode != null || index < values.size() - 1;
    }
    
    public int next() {
        ++index;
        if (index == values.size()) {
            while (currNode != null) {
                nodeStack.push(currNode);
                currNode = currNode.left;                
            }
            TreeNode nextNode = nodeStack.pop();
            currNode = nextNode.right;
        
            values.add(nextNode.val);
        }
            
        return values.get(index);
    }
    
    public boolean hasPrev() {
        return index > 0;
    }
    
    public int prev() {
        --index;
        return values.get(index);
    }
}

class BinarySearchTreeIterator:

    def __init__(self, root: TreeNode):
        self.current = root
        self.nodes_stack, self.values = [], []
        self.index = -1

    def hasNext(self) -> bool:
        return self.nodes_stack or self.current or self.index < len(self.values) - 1

    def next(self) -> int:
        self.index += 1
        
        if self.index == len(self.values):
            while self.current:
                self.nodes_stack.append(self.current)
                self.current = self.current.left
            node = self.nodes_stack.pop()
            self.current = node.right
            self.values.append(node.val)
        
        return self.values[self.index]

    def hasPrev(self) -> bool:
        return self.index > 0

    def prev(self) -> int:
        self.index -= 1
        return self.values[self.index]