Problem Statement

Implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (BST):

• BSTIterator(TreeNode root) Initializes an object of the BSTIterator class. The root of the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST.
• boolean hasNext() Returns true if there exists a number in the traversal to the right of the pointer, otherwise returns false.
• int next() Moves the pointer to the right, then returns the number at the pointer.

Notice that by initializing the pointer to a non-existent smallest number, the first call to the next() will return the smallest element in the BST.

Assume that the next() calls will always be valid. That is, there will be at least a next number in the in-order traversal when the next() is called.

Examples

Example 1:

Input : [ "BSTIterator" , "next" , "next" , "hasNext" , "next" , "hasNext" , "next" , "hasNext" , "next" , "hasNext" ] , root = [7, 3, 15, null, null, 9, 20]
Output : [3, 7, true, 9, true, 15, true, 20, false]

Explanation :
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next();  // return 3
bSTIterator.next();  // return 7
bSTIterator.hasNext(); // return True
bSTIterator.next();  // return 9
bSTIterator.hasNext(); // return True
bSTIterator.next();  // return 15
bSTIterator.hasNext(); // return True
bSTIterator.next();  // return 20
bSTIterator.hasNext(); // return False

Example 2:

Input : [ "BSTIterator" , "next" , "next" , "next", "hasNext" , "next" , "hasNext" ] , root = [7, 3, 15, null, null, 9, 20]
Output : [3, 7, 9, true, 15, true]

Explanation :
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next();  // return 3
bSTIterator.next();  // return 7
bSTIterator.next(); // return 9
bSTIterator.hasNext(); // return True
bSTIterator.next();  // return 15
bSTIterator.hasNext(); // return True

Different Approaches

1️⃣ Brute Force Approach

Intuition:

When performing an inorder traversal on a Binary Search Tree (BST), the result is a sorted list of node values. By storing these values in an array, it's possible to easily access them in ascending order. The BSTIterator class leverages this idea by maintaining an index to track the current position within the array. This index is initialized to -1, and with each call to next(), the index is incremented to provide the next element in the sorted sequence.

Approach:

1. Execute an inorder traversal of the BST and store the node values in an array. This involves recursively visiting the left subtree, the current node, and then the right subtree.
2. In the BSTIterator() constructor, initialize an index variable to -1. This variable will keep track of the current position within the array.
3. Implement the next() function to increment the index by 1 and return the value at the updated index from the inorder traversal array.
4. Implement the hasNext() function to return true if index + 1 is less than the length of the inorder traversal array; otherwise, return false.

Code:

#include <bits/stdc++.h>
using namespace std;

//Definition for a binary tree node.
 struct TreeNode {
     int data;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};


// Class for BST Iterator
class BSTIterator {
public:
    // Constructor to initialize the iterator
    BSTIterator(TreeNode* root) {
        // Perform inorder traversal and store values
        inorderTraversal(root);
        // Initialize index to -1 (before first element)
        index = -1;
    }
    
    // Check if there are more elements in the BST
    bool hasNext() {
        // True if there are more elements
        return index + 1 < values.size();
    }
    
    // Return the next element in the BST
    int next() {
        // Increment index and return the next value
        return values[++index];
    }

private:
    // Vector to store inorder traversal values
    vector<int> values;
    // Index to track the current position
    int index;

    // Helper function to perform inorder traversal
    void inorderTraversal(TreeNode* node) {
        // Base case: if node is null, return
        if (node == nullptr) return;
        // Recur on the left subtree
        inorderTraversal(node->left);
        // Add the current node's value to the vector
        values.push_back(node->data);
        // Recur on the right subtree
        inorderTraversal(node->right);
    }
};

// Main method to demonstrate the usage of BSTIterator
int main() {
    // Create a sample binary search tree
    TreeNode* root = new TreeNode(7);
    root->left = new TreeNode(3);
    root->right = new TreeNode(15);
    root->right->left = new TreeNode(9);
    root->right->right = new TreeNode(20);

    // Instantiate the BSTIterator with the root of the tree
    BSTIterator* iterator = new BSTIterator(root);

    // Use the iterator to get the elements in sorted order
    while (iterator->hasNext()) {
        cout << iterator->next() << " ";
    }

    // Output: 3 7 9 15 20

    return 0;
}

Complexity Analysis:

• Time Complexity:O(N) where n is the number of nodes in the tree for inorder traversal and constant time O(1) for hasNext and next.
• Space Complexity: O(N) due to the storage of values from the inorder traversal in an array.

2️⃣ Optimal Approach

Intuition:

While a previous approach used O(N) space complexity, it can be optimized to O(H) space complexity, where H is the height of the tree, by utilizing the properties of a Binary Search Tree (BST). This method creates an iterator that uses a stack to manage the traversal, resulting in efficient O(1) time complexity for the next() and hasNext() operations. By initially traversing to the leftmost node and maintaining a stack of nodes, the BST can be iterated over efficiently.

Approach:

1. Constructor BSTIterator(TreeNode root):
   1. Use a stack (Last In First Out) within the constructor.
   2. Start from the root and traverse to the leftmost node, pushing each encountered node onto the stack.
2. next() function:
   1. Pop the top element from the stack.
   2. Move to the right subtree of the popped node and traverse down its left subtree, pushing encountered nodes onto the stack.
   3. Return the value of the popped node.
3. hasNext() function:
   1. Check if the stack is not empty.
   2. If the stack contains elements, return true, indicating there are more nodes to iterate over.
   3. If the stack is empty, return false, indicating there are no more nodes to iterate over.

Code:

#include <bits/stdc++.h>
using namespace std;

// Definition for a binary tree node
struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int val) : data(val), left(NULL), right(NULL) {}
};

class BSTIterator {
    stack<TreeNode*> myStack;

public:
    // Constructor initializes the iterator on the root of the BST
    BSTIterator(TreeNode* root) {
        pushAll(root);
    }
    
    // Returns true if there is a next element in the iterator
    bool hasNext() {
        return !myStack.empty();
    }
    
    // Returns the next smallest element in the BST
    int next() {
        TreeNode* temp = myStack.top();
        myStack.pop();
        pushAll(temp->right);
        return temp->data;
    }

private:
    // Helper function to push all the left nodes onto the stack
    void pushAll(TreeNode* node) {
        for (; node != NULL; myStack.push(node), node = node->left);
    }
};

// Main function to demonstrate the BSTIterator
int main() {
    TreeNode* root = new TreeNode(7);
    root->left = new TreeNode(3);
    root->right = new TreeNode(15);
    root->right->left = new TreeNode(9);
    root->right->right = new TreeNode(20);

    BSTIterator* iterator = new BSTIterator(root);
    while (iterator->hasNext()) {
        cout << iterator->next() << " ";
    }

    // Clean up memory
    delete iterator;
    delete root->left;
    delete root->right->left;
    delete root->right->right;
    delete root->right;
    delete root;

    return 0;
}

Complexity Analysis:

• Time Complexity:O(1) as next() and hasNext() occur is constant time, the element pushed onto the stack during traversal to the leftmost node and during subsequent traversals will take O(H) time for each traversal.
• Space Complexity:O(H), where H is the height of the tree. This is because, in the worst case, the stack can contain all the nodes from the root to the leftmost leaf node