Binary Search Tree Iterator

Problem Statement

The task is to implement a BSTIterator class that allows iterating over a binary search tree (BST) using its in-order traversal. The key operations provided by this iterator are:

• BSTIterator(TreeNode root) - This constructor initializes a new iterator object, receiving the root of the BST. A pointer is used to manage the traversal and is initially set before the smallest element.
• boolean hasNext() - Checks and returns true if there are more elements to iterate over in the BST to the right of the current position of the pointer.
• int next() - Moves the pointer to the right and returns the current element at the pointer after the move.

The iterator cleverly uses the natural ordering of elements in a BST to systematically access each element in ascending order. When the next() method is initially called, it yields the smallest element in the BST, ensuring intuitive and predictable behavior of the iterator.

Examples

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:

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

2. bSTIterator.next(); ➜ returns 3

3. bSTIterator.next(); ➜ returns 7

4. bSTIterator.hasNext(); ➜ returns true

5. bSTIterator.next(); ➜ returns 9

6. bSTIterator.hasNext(); ➜ returns true

7. bSTIterator.next(); ➜ returns 15

8. bSTIterator.hasNext(); ➜ returns true

9. bSTIterator.next(); ➜ returns 20

10. bSTIterator.hasNext(); ➜ returns false

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

Approach and Intuition

The BSTIterator leverages the properties of in-order traversal, which processes elements of a BST in non-decreasing order. This is achieved by using the following approach:

1. Initialization with Stack:

   • During the initialization (BSTIterator), a stack is prepared to simulate the recursive nature of in-order traversal iteratively. This stack manages the current nodes to be processed.
   • Begin from the given root and push all left children onto the stack, reaching the minimum element first.

2. Element Retrieval (next method):

   • To retrieve the next element in order, the top node of the stack is popped. This node corresponds to the next smallest element.
   • If the popped node has a right subtree, proceed to push all of its left children onto the stack (similar to the initialization process). This step ensures that the next smallest element is correctly lined up for subsequent calls.

3. Checking Continuation (hasNext method):

   • This simply checks whether there are any elements left in the stack. A non-empty stack indicates that there are further elements to process in the traversal, hence hasNext returns true.
   • If the stack is empty, it returns false indicating that the traversal is complete.

Through this approach, the class efficiently manages the traversal's state without needing to store the entire traversal results upfront. This makes it particularly memory-efficient for large trees. Each call to next() works in amortized O(1) time, maintaining the stack with the next elements to be processed.

Given the constraints, this method is well-suited as it processes nodes on-demand and handles up to 105 calls efficiently. The example given clearly illustrates the functioning of the iterator under typical scenarios. The sequence of operations and their results match the expected outcome based on in-order traversal logic.

Solutions

class BinarySearchTreeIterator {
public:
    stack<TreeNode*> nodeStack;
    
    BinarySearchTreeIterator(TreeNode* root) {
        this->pushAllLeft(root);
    }
    
    void pushAllLeft(TreeNode* node) {
        while (node != NULL) {
            this->nodeStack.push(node);
            node = node->left;
        }
    }
    
    int next() {
        TreeNode* smallestNode = this->nodeStack.top();
        this->nodeStack.pop();
    
        if (smallestNode->right != NULL) {
            this->pushAllLeft(smallestNode->right);
        }
    
        return smallestNode->val;
    }
    
    bool hasNext() { return !this->nodeStack.empty(); }
};