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 code below, what is the output sequence of the Next() calls?

DSA C#

public class TreeNode {
    public int val;
    public TreeNode left, right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class BSTIterator {
    private Stack<TreeNode> stack = new Stack<TreeNode>();

    public BSTIterator(TreeNode root) {
        PushLeft(root);
    }

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

    public int Next() {
        TreeNode node = stack.Pop();
        PushLeft(node.right);
        return node.val;
    }

    public bool HasNext() {
        return stack.Count > 0;
    }
}

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

TreeNode root = new TreeNode(7,
    new TreeNode(3),
    new TreeNode(15, new TreeNode(9), new TreeNode(20))
);
BSTIterator iterator = new BSTIterator(root);

List<int> result = new List<int>();
while (iterator.HasNext()) {
    result.Add(iterator.Next());
}
Console.WriteLine(string.Join(", ", result));

A 7, 9, 3, 15, 20

B 3, 7, 9, 15, 20

C 3, 7, 15, 9, 20

D 7, 3, 15, 9, 20

💡 Hint

Think about how in-order traversal visits nodes in ascending order.

The BST Iterator uses an in-order traversal approach. It pushes all left children first, so the smallest element (3) is returned first, then 7, then 9, 15, and finally 20.

🧠 Conceptual

intermediate

BST Iterator Space Complexity

What is the worst-case space complexity of the BST Iterator implemented with a stack for a BST with n nodes?

A O(n log n), due to repeated stack operations

B O(log n), always, because the stack only stores nodes along one path

C O(1), since the iterator uses constant extra space

D O(n), when the BST is skewed and all nodes are pushed onto the stack

💡 Hint

Consider the shape of the tree and how many nodes can be on the stack at once.

In the worst case, the BST is skewed (like a linked list), so all nodes are pushed onto the stack, leading to O(n) space complexity.

🔧 Debug

advanced

Identify the Bug in BST Iterator Next Method

What error will occur when calling Next() on this BST Iterator implementation if the stack is empty?

DSA C#

public int Next() {
    TreeNode node = stack.Pop();
    PushLeft(node.right);
    return node.val;
}

A IndexOutOfRangeException because stack index is invalid

B NullReferenceException because node.right is null

C InvalidOperationException because Pop() is called on an empty stack

D No error; it returns default value 0

💡 Hint

What happens if you pop from an empty stack in C#?

Calling Pop() on an empty stack throws InvalidOperationException in C#.

🚀 Application

advanced

Using BST Iterator to Find kth Smallest Element

How can you use the BST Iterator to find the kth smallest element in a BST?

A Call Next() k times and return the last value returned

B Push all nodes to a list and sort it, then return kth element

C Traverse the BST recursively k times and return the kth node

D Call HasNext() k times and return the last value from HasNext()

💡 Hint

The iterator returns nodes in ascending order.

Calling Next() k times returns nodes in ascending order, so the kth call returns the kth smallest element.

🧠 Conceptual

expert

BST Iterator Behavior with Concurrent Modifications

What is the expected behavior if the BST is modified (nodes added or removed) after the BST Iterator is created and before all elements are iterated?

A The iterator may produce incorrect results or throw exceptions because it does not track modifications

B The iterator automatically updates to reflect changes in the BST

C The iterator resets and starts from the new root after modification

D The iterator ignores modifications and continues safely with original nodes

💡 Hint

Think about how the stack stores nodes and if it knows about tree changes.

The iterator uses a stack of nodes from the original tree structure. If the tree changes, the iterator's stack may become invalid, causing wrong results or exceptions.

Practice

1. What is the main purpose of a BST Iterator in data structures?

easy

A. To insert new nodes into the BST

B. To balance the BST automatically

C. To delete nodes from the BST

D. To traverse the BST in ascending order without recursion

Solution

1. Step 1: Understand BST Iterator functionality

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

2. Step 2: Identify the main purpose

   Among the options, only traversing in ascending order without recursion matches the BST Iterator's role.

3. Final Answer:

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

4. Quick Check:

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

Hint: BST Iterator helps traverse nodes in sorted order easily [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 C# method signature for the Next() method in a BST Iterator class that returns the next smallest integer?

easy

A. public string Next()

B. public void Next()

C. public int Next()

D. public bool Next()

Solution

1. Step 1: Determine the return type of Next()

   The Next() method should return the next smallest integer value from the BST, so its return type must be int.

2. Step 2: Check method signature correctness

   Only public int Next() matches the expected signature returning an integer value.

3. Final Answer:

   public int Next() -> Option C

4. Quick Check:

   Next() returns int value [OK]

Hint: Next() returns the next smallest value as int [OK]

Common Mistakes:

• Using void return type for Next()
• Returning bool instead of int
• Returning string instead of int

3. Given the BST with nodes inserted in this order: 7, 3, 15, 9, 20. What is the output sequence of calling Next() five times on a correctly implemented BST Iterator?

medium

A. [7, 3, 15, 9, 20]

B. [3, 7, 9, 15, 20]

C. [20, 15, 9, 7, 3]

D. [3, 9, 7, 15, 20]

Solution

1. Step 1: Construct BST and find in-order traversal

   Inserting 7, 3, 15, 9, 20 creates BST:
   7 is root
   3 left of 7
   15 right of 7
   9 left of 15
   20 right of 15
   In-order traversal (left-root-right) is [3, 7, 9, 15, 20].

2. Step 2: Understand Next() output sequence

   Calling Next() five times returns nodes in in-order sequence: 3, 7, 9, 15, 20.

3. Final Answer:

   [3, 7, 9, 15, 20] -> Option B

4. Quick Check:

   In-order traversal = Next() outputs [3,7,9,15,20] [OK]

Hint: Next() outputs nodes in ascending order [OK]

Common Mistakes:

• Confusing insertion order with traversal order
• Reversing the output sequence
• Mixing left and right subtree nodes

4. Identify the bug in this BST Iterator Next() method snippet and choose the correct fix:

public int Next() {
    TreeNode node = stack.Pop();
    if (node.right != null) {
        stack.Push(node.right);
    }
    return node.val;
}

medium

A. Push all left children of node.right onto stack, not just node.right

B. Pop from stack only if it is not empty

C. Return node.val before popping from stack

D. Check node.left instead of node.right

Solution

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

   After popping node, if node.right exists, we must push node.right and all its left descendants to maintain in-order traversal.

2. Step 2: Identify missing step

   Current code pushes only node.right, missing its left subtree nodes, causing incorrect traversal order.

3. Final Answer:

   Push all left children of node.right onto stack, not just node.right -> Option A

4. Quick Check:

   Push left subtree nodes after right child [OK]

Hint: Always push left children of right subtree after popping [OK]

Common Mistakes:

• Pushing only right child without left descendants
• Returning value before popping
• Checking left child instead of right child

5. You want to design a BST Iterator that supports HasNext() and Next() methods with O(1) average time per call and O(h) space, where h is tree height. Which approach best achieves this?

hard

A. Use a stack to store left children nodes and push left descendants of right child on Next()

B. Store all nodes in a list during initialization and iterate over the list

C. Use recursion inside Next() to find next node each time

D. Use a queue to store nodes in level order traversal

Solution

1. Step 1: Understand time and space constraints

   O(1) average time per call and O(h) space means we cannot store all nodes upfront or use recursion each call.

2. Step 2: Evaluate approaches

   Using a stack to store left children and pushing left descendants of right child on Next() achieves these constraints efficiently.

3. Final Answer:

   Use a stack to store left children nodes and push left descendants of right child on Next() -> Option A

4. Quick Check:

   Stack with left children = O(1) avg time, O(h) space [OK]

Hint: Stack with left children keeps O(h) space and O(1) average time [OK]

Common Mistakes:

• Storing all nodes wastes O(n) space
• Using recursion causes higher time complexity
• Using queue breaks in-order traversal order