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).

Practice

1. What is the main purpose of a BST Iterator in the context of a Binary Search Tree?

easy

A. To traverse the BST in ascending order without recursion

B. To insert new nodes into the BST

C. To delete nodes from the BST

D. To balance the BST automatically

Solution

1. Step 1: Understand BST Iterator functionality

   A BST Iterator is designed to traverse the tree in sorted order, typically ascending, without using recursion explicitly.

2. Step 2: Identify the main purpose

   It provides a way to get the next smallest element efficiently, which matches To traverse the BST in ascending order without recursion.

3. Final Answer:

   To traverse the BST in ascending order without recursion -> Option A

4. Quick Check:

   BST Iterator = In-order traversal without recursion [OK]

Hint: BST Iterator returns next smallest element in sorted order [OK]

Common Mistakes:

• Confusing iterator with insertion or deletion operations
• Thinking it balances the tree automatically
• Assuming it uses recursion internally

2. Which of the following is the correct way to declare a stack to be used in a BST Iterator in C++?

easy

A. stack s;

B. stack<int> s;

C. stack<TreeNode> s;

D. stack s;

Solution

1. Step 1: Identify the data type stored in the stack

   The BST Iterator stores pointers to tree nodes to traverse the tree efficiently, so the stack should hold TreeNode pointers.

2. Step 2: Match the correct syntax

   stack s; uses stack which is correct. stack<int> s; uses int, which is incorrect. stack<TreeNode> s; uses TreeNode by value, which is inefficient. stack s; uses Node*, which is undefined here.

3. Final Answer:

   stack s; -> Option D

4. Quick Check:

   Stack stores pointers to TreeNode [OK]

Hint: Stack must hold pointers to tree nodes, not values [OK]

Common Mistakes:

• Using stack of int instead of TreeNode*
• Using stack of TreeNode by value causing copies
• Using undefined Node* type

3. Given the following BST Iterator code snippet, what will be the output sequence of calls to next()?

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

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

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

BSTIterator it(root);
while(it.hasNext()) {
  cout << it.next() << " ";
}

medium

A. 20 15 9 7 3

B. 7 3 15 9 20

C. 3 7 9 15 20

D. 3 9 7 15 20

Solution

1. Step 1: Understand the BST structure and in-order traversal

   The BST is: 7 / \ 3 15 / \ 9 20 In-order traversal visits nodes in ascending order: 3, 7, 9, 15, 20.

2. Step 2: Trace the iterator's next() calls

   Iterator pushes left nodes first, so initial stack: 7, 3 (top). Calls to next() pop 3, then 7, then push left of 7's right (15), then 9, then 15, then 20. Output sequence matches 3 7 9 15 20.

3. Final Answer:

   3 7 9 15 20 -> Option C

4. Quick Check:

   In-order traversal = 3 7 9 15 20 [OK]

Hint: BST Iterator outputs nodes in ascending order (in-order) [OK]

Common Mistakes:

• Confusing pre-order or post-order traversal output
• Not pushing left children correctly
• Misunderstanding stack top element order

4. Identify the bug in the following BST Iterator next() method and select the correct fix:

int next() {
  TreeNode* node = s.top();
  s.pop();
  pushLeft(node->left); // Bug here
  return node->val;
}

medium

A. Remove pushLeft call completely

B. Change pushLeft(node->left) to pushLeft(node->right)

C. Change s.pop() to s.pop(node)

D. Add check if node is nullptr before pushLeft

Solution

1. Step 1: Analyze the next() method logic

   After popping the current node, the iterator should push all left children of the right subtree to continue in-order traversal.

2. Step 2: Identify the incorrect call

   The code incorrectly calls pushLeft(node->left), which revisits the left subtree already processed. It should call pushLeft(node->right) to process the right subtree.

3. Final Answer:

   Change pushLeft(node->left) to pushLeft(node->right) -> Option B

4. Quick Check:

   Push left of right subtree after pop [OK]

Hint: Push left nodes of right child after popping [OK]

Common Mistakes:

• Pushing left subtree again causing infinite loop
• Removing pushLeft call causing incomplete traversal
• Incorrect pop syntax causing compile error

5. You want to design a BST Iterator that supports a method peek() which returns the next smallest element without advancing the iterator. How would you modify the existing BST Iterator design to support peek() efficiently?

hard

A. Store the next smallest element in a variable during next() and return it in peek()

B. Use an additional stack to store peeked elements separately

C. Modify next() to not pop from stack and peek() to pop instead

D. Precompute all elements in sorted order and store in a vector

Solution

1. Step 1: Understand peek() requirement

   peek() should return next smallest element without moving the iterator forward, so it must remember the next element.

2. Step 2: Modify iterator to store next element

   By storing the next smallest element in a variable during next(), peek() can return this stored value without popping or changing the stack.

3. Step 3: Evaluate other options

   Using an extra stack or precomputing all elements wastes space or changes iterator behavior. Modifying next() to not pop breaks standard iteration.

4. Final Answer:

   Store the next smallest element in a variable during next() and return it in peek() -> Option A

5. Quick Check:

   Cache next element for peek() [OK]

Hint: Cache next element on next() call for peek() [OK]

Common Mistakes:

• Precomputing all elements wastes memory
• Changing next() behavior breaks iteration
• Using extra stack complicates design unnecessarily