BST Iterator Design in DSA C# - Build from Scratch

BST Iterator Design

📖 Scenario: Imagine you have a large collection of numbers stored in a Binary Search Tree (BST). You want to look at these numbers one by one in ascending order without loading them all at once. This is like flipping through pages of a book, seeing one page at a time.

🎯 Goal: You will build a BSTIterator class in C# that helps you move through the BST numbers in order. It will have two main actions: Next() to get the next smallest number, and HasNext() to check if more numbers are left.

📋 What You'll Learn

Create a TreeNode class to represent nodes in the BST with int val, TreeNode left, and TreeNode right.

Create a BSTIterator class with a constructor that takes the root TreeNode.

Implement HasNext() method that returns true if there is a next smallest number.

Implement Next() method that returns the next smallest number in the BST.

Use a stack to help traverse the BST in ascending order without recursion.

💡 Why This Matters

🌍 Real World

BST iterators are used in databases and search engines to efficiently access sorted data without loading everything into memory.

💼 Career

Understanding BST iterators helps in roles involving data structure optimization, backend development, and algorithm design.

1

Create the TreeNode class and sample BST

Create a class called TreeNode with an integer val, and two TreeNode references called left and right. Then create a BST with root node root having value 7, left child 3, and right child 15. The right child 15 should have two children: left child 9 and right child 20.

DSA C#

# Define TreeNode class and create the BST as described
# Your code here

Hint

Think of TreeNode as a box holding a number and links to two smaller boxes (left and right). Build the tree from the top (root) down.

2

Add stack and constructor for BSTIterator

Create a class called BSTIterator with a private Stack<TreeNode> called stack. Add a constructor that takes a TreeNode root and calls a private method PushLeft(TreeNode node) to push all left children of root onto the stack.

DSA C#

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

    public BSTIterator(TreeNode root)
    {
        // Call PushLeft with root
        // Your code here
    }

    private void PushLeft(TreeNode node)
    {
        // Your code here
    }
}

Hint

Use a stack to remember nodes. Push all left nodes starting from root to get the smallest first.

3

Implement HasNext() and Next() methods

Inside BSTIterator, implement a public method bool HasNext() that returns true if stack.Count is greater than zero. Also implement a public method int Next() that pops the top node from the stack, calls PushLeft on its right child, and returns the popped node's value.

DSA C#

public bool HasNext()
{
    // Your code here
}

public int Next()
{
    // Your code here
}

Hint

HasNext() checks if stack is not empty. Next() pops the top node, pushes left children of its right child, and returns the node's value.

4

Use BSTIterator to print all elements in ascending order

Create a BSTIterator object called iterator using the root. Use a while loop that runs while iterator.HasNext() is true. Inside the loop, print the result of iterator.Next() followed by a space.

DSA C#

BSTIterator iterator = new BSTIterator(root);

// Use while loop to print all elements in ascending order
// Your code here

Hint

Use the iterator to get each next smallest number and print it with a space.

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