BST Iterator Design in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of BST Iterator next() calls

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

DSA Java

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

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

BSTIterator iterator = new BSTIterator(root); // root is the above tree

System.out.print(iterator.next() + ", ");
System.out.print(iterator.next() + ", ");
System.out.print(iterator.next());

A 3, 7, 9

B 3, 9, 7

C 7, 3, 9

D 7, 9, 15

💡 Hint

Remember, BST Iterator returns elements in ascending order.

The BST Iterator returns the next smallest element each time next() is called. The in-order traversal of the tree is 3, 7, 9, 15, 20. So the first three next() calls return 3, 7, and 9.

🧠 Conceptual

intermediate

Understanding BST Iterator hasNext() behavior

If a BST Iterator is initialized with a BST containing nodes [5, 3, 7], and next() has been called twice, what will hasNext() return?

A false

B Throws an exception

C true

D Depends on the implementation

💡 Hint

Think about how many nodes remain after two next() calls.

The BST has three nodes. After calling next() twice, one node remains unvisited. So hasNext() returns true.

🔧 Debug

advanced

Identify the bug in BST Iterator next() method

What error will occur when running the following next() method code snippet in a BST Iterator?

DSA Java

public int next() {
    TreeNode node = stack.pop();
    if (node.right != null) {
        pushLeft(node.right);
    }
    return node.val;
}

private void pushLeft(TreeNode node) {
    while (node != null) {
        stack.push(node);
        node = node.left;
    }
}

A StackOverflowError due to recursion

B NullPointerException if stack is empty

C Infinite loop in pushLeft method

D No error, works correctly

💡 Hint

Check how the stack is used and how pushLeft works.

The code correctly pops the top node, pushes all left children of the right subtree, and returns the node's value. No errors occur if stack is managed properly.

❓ Predict Output

advanced

Output after full iteration of BST Iterator

What is the output of printing all elements using BST Iterator's next() until hasNext() returns false for the BST below?

DSA Java

// BST structure:
//       10
//      /  \
//     5    15
//    / \     \
//   3   7     18

BSTIterator iterator = new BSTIterator(root);
while(iterator.hasNext()) {
    System.out.print(iterator.next() + " ");
}

A 5 3 7 10 15 18

B 3 5 7 10 15 18

C 3 7 5 10 15 18

D 10 5 3 7 15 18

💡 Hint

BST Iterator returns nodes in ascending order.

The in-order traversal of the BST is 3, 5, 7, 10, 15, 18. The iterator prints nodes in this order.

🧠 Conceptual

expert

Space complexity of BST Iterator

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

A O(h), where h is the height of the BST

B O(n), where n is the number of nodes in the BST

C O(log n), assuming the BST is balanced

D O(1), constant space

💡 Hint

Consider how many nodes can be on the stack at once during traversal.

The stack stores nodes along the path from root to the current node, which is at most the height h of the tree. So space complexity is O(h).

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 = Ascending traversal [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 method signature for the next() method in a BST Iterator class in Java?

easy

A. public Node next()

B. public void next()

C. public int next()

D. public boolean next()

Solution

1. Step 1: Understand the return type of next()

   The next() method returns the next smallest integer value from the BST, so it should return an int.

2. Step 2: Match method signature

   public int next() matches the expected signature: public int next().

3. Final Answer:

   public int next() -> Option C

4. Quick Check:

   next() returns int value [OK]

Hint: next() returns next smallest int value from BST [OK]

Common Mistakes:

• Using void return type for next()
• Returning boolean instead of int
• Returning Node instead of int value

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

BSTIterator iterator = new BSTIterator(root); // BST with nodes 3, 7, 9
System.out.print(iterator.next() + ", ");
System.out.print(iterator.next() + ", ");
System.out.print(iterator.next());

medium

A. 7, 3, 9

B. 3, 7, 9

C. 9, 7, 3

D. 3, 9, 7

Solution

1. Step 1: Understand BST in-order traversal order

   BST in-order traversal returns nodes in ascending order: 3, 7, 9.

2. Step 2: Trace next() calls

   Each next() call returns the next smallest element, so the output is 3, then 7, then 9.

3. Final Answer:

   3, 7, 9 -> Option B

4. Quick Check:

   In-order traversal = 3,7,9 [OK]

Hint: next() returns ascending BST values in order [OK]

Common Mistakes:

• Assuming next() returns descending order
• Mixing up node values order
• Confusing next() with hasNext()

4. Identify the bug in this BST Iterator next() method implementation:

public int next() {
    TreeNode node = stack.pop();
    if (node.right != null) {
        pushLeft(node.right);
    }
    return node.val;
}

private void pushLeft(TreeNode node) {
    while (node != null) {
        stack.push(node);
        node = node.left;
    }
}

medium

A. The next() method should return node.right.val instead of node.val

B. The pushLeft method should push right children instead of left

C. The stack is not initialized before use

D. The next() method should check if stack is empty before popping

Solution

1. Step 1: Analyze next() method stack usage

   Calling stack.pop() without checking if stack is empty can cause runtime error if no elements remain.

2. Step 2: Identify missing safety check

   Proper implementation should check stack emptiness before popping to avoid exceptions.

3. Final Answer:

   The next() method should check if stack is empty before popping -> Option D

4. Quick Check:

   Check stack empty before pop [OK]

Hint: Always check stack not empty before pop in next() [OK]

Common Mistakes:

• Ignoring stack empty check causing exceptions
• Misunderstanding pushLeft logic
• Returning wrong node value

5. You want to design a BST Iterator that supports peek() to see the next smallest element without advancing the iterator. Which approach correctly extends the standard BST Iterator design?

hard

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

B. Use an extra stack to store all nodes and pop from it in peek()

C. Modify next() to return the top of the stack without popping it, and peek() pops the stack

D. Traverse the entire BST in constructor and store values in a list for peek() and next()

Solution

1. Step 1: Understand peek() requirement

   peek() should return next smallest element without advancing iterator, so it must not pop stack.

2. Step 2: Identify correct approach

   Storing next smallest element in a variable during next() allows peek() to return it without changing stack state, matching Store the next smallest element in a variable during next() and return it in peek() without popping stack.

3. Final Answer:

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

4. Quick Check:

   peek() returns next without advancing [OK]

Hint: Cache next element to support peek() without stack pop [OK]

Common Mistakes:

• Popping stack in peek() advancing iterator
• Using extra stack unnecessarily
• Precomputing all values losing iterator benefits