BST Iterator Design in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of BST Iterator next() calls

Given the BST Iterator initialized with the root of the BST below, what is the output sequence of calling next() three times?

DSA C++

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class BSTIterator {
    stack<TreeNode*> st;
    void pushLeft(TreeNode* node) {
        while (node) {
            st.push(node);
            node = node->left;
        }
    }
public:
    BSTIterator(TreeNode* root) { pushLeft(root); }
    int next() {
        TreeNode* node = st.top(); st.pop();
        pushLeft(node->right);
        return node->val;
    }
    bool hasNext() { return !st.empty(); }
};

// BST structure:
//       7
//      / \
//     3   15
//         / \
//        9  20

// Iterator initialized with root (7)
// Calls: next(), next(), next()

A [3, 7, 9]

B [7, 3, 9]

C [3, 9, 7]

D [7, 9, 15]

💡 Hint

Remember that BST Iterator returns nodes in ascending order (inorder traversal).

The iterator pushes all left nodes first: stack initially has 7, then 3. Calling next() returns 3, then pushes right subtree of 3 (none). Next next() returns 7, then pushes left nodes of 7's right child (15), so stack has 15 and its left child 9. Next next() returns 9.

🧠 Conceptual

intermediate

Space complexity of BST Iterator

What is the worst-case space complexity of the BST Iterator implemented using a stack to simulate inorder traversal on a BST with n nodes?

A O(n^2), due to repeated stack operations

B O(log n), always regardless of tree shape

C O(n), when the BST is skewed (like a linked list)

D O(1), because it uses constant extra space

💡 Hint

Consider the maximum height of the stack during traversal.

In the worst case, the BST is skewed (all nodes have only one child), so the stack can hold all nodes along the path, which is O(n). For balanced trees, it's O(log n).

🔧 Debug

advanced

Identify the error in BST Iterator next() method

What error will occur when running the following next() method in BST Iterator if the stack is empty?

DSA C++

int next() {
    TreeNode* node = st.top();
    st.pop();
    pushLeft(node->right);
    return node->val;
}

A Runtime error: accessing top of empty stack

B Compilation error: missing return statement

C Logical error: returns wrong node value

D No error, works fine even if stack is empty

💡 Hint

What happens if next() is called when hasNext() is false?

Calling st.top() on an empty stack causes a runtime error (undefined behavior). The code assumes next() is called only if hasNext() is true.

🚀 Application

advanced

Using BST Iterator to find kth smallest element

Which code snippet correctly uses BST Iterator to find the kth smallest element in a BST?

A

BSTIterator it(root);
int val = 0;
for (int i = 1; i <= k; i++) {
    val = it.next();
}
return val + 1;

B

BSTIterator it(root);
int val = -1;
for (int i = 0; i < k; i++) {
    val = it.next();
}
return val;

C

BSTIterator it(root);
int count = 0;
while (count < k) {
    it.next();
    count++;
}
return it.next();

D

BSTIterator it(root);
int val = -1;
while (it.hasNext()) {
    val = it.next();
    if (val == k) break;
}
return val;

💡 Hint

The kth smallest is the value returned by the kth call to next().

Option B calls next() exactly k times and returns the last value, which is the kth smallest. Option B compares value to k incorrectly. Option B calls next() one extra time. Option B adds 1 incorrectly.

❓ Predict Output

expert

Output after mixed hasNext() and next() calls

Given the BST Iterator initialized with the root of the BST below, what is the output of the following calls sequence? hasNext(), next(), next(), hasNext(), next(), hasNext()

DSA C++

// BST structure:
//       5
//      / \
//     3   7
//    /   / \
//   2   6   8

// Calls sequence:
// hasNext(), next(), next(), hasNext(), next(), hasNext()

A [true, 2, 3, true, 5, false]

B [false, 2, 3, true, 5, true]

C [true, 2, 3, false, 5, true]

D [true, 2, 3, true, 5, true]

💡 Hint

Track the stack and returned values carefully after each call.

Initially stack has 5,3,2. hasNext() true. next() returns 2. next() returns 3. hasNext() true (stack has 5). next() returns 5 (pushes 7,6 onto stack). hasNext() true (stack not empty).