BST Iterator Design in DSA C#

Mental Model

A BST iterator lets you see the tree's values one by one in order, like reading a book page by page without jumping around.

Analogy: Imagine a bookmark in a book that helps you remember where you stopped reading. Each time you open the book, you continue from that bookmark to the next page in order.

      4
     / \
    2   6
   / \ / \
  1  3 5  7
↑ stack holds left path nodes for next smallest

Dry Run Walkthrough

Input: BST with nodes 4,2,6,1,3,5,7; iterate through all nodes in ascending order

Goal: Visit all nodes in ascending order using the iterator's next() method

Step 1: Initialize iterator by pushing left path from root (4) to stack

stack: [4, 2, 1]
next node to return: 1

Why: We push left children to reach the smallest node first

Step 2: Call next(), pop 1 from stack, 1 has no right child

stack: [4, 2]
returned: 1

Why: 1 is the smallest node, no right subtree to explore

Step 3: Call next(), pop 2 from stack, push left path of 2's right child (3)

stack: [4, 3]
returned: 2

Why: After 2, next smallest is 3 from right subtree

Step 4: Call next(), pop 3 from stack, 3 has no right child

stack: [4]
returned: 3

Why: 3 is next smallest, no right subtree

Step 5: Call next(), pop 4 from stack, push left path of 4's right child (6,5)

stack: [6, 5]
returned: 4

Why: After 4, next smallest is 5 from right subtree

Step 6: Call next(), pop 5 from stack, 5 has no right child

stack: [6]
returned: 5

Why: 5 is next smallest, no right subtree

Step 7: Call next(), pop 6 from stack, push left path of 6's right child (7)

stack: [7]
returned: 6

Why: After 6, next smallest is 7 from right subtree

Step 8: Call next(), pop 7 from stack, 7 has no right child

stack: []
returned: 7

Why: 7 is the largest node, iteration ends

Result:

stack: []
returned sequence: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode 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) {
        PushLeftPath(root);
    }

    private void PushLeftPath(TreeNode node) {
        while (node != null) {
            stack.Push(node); // push current node to stack
            node = node.left;  // move to left child
        }
    }

    public bool HasNext() {
        return stack.Count > 0; // check if any nodes left
    }

    public int Next() {
        TreeNode curr = stack.Pop(); // pop top node as next smallest
        if (curr.right != null) {
            PushLeftPath(curr.right); // push left path of right subtree
        }
        return curr.val; // return current node's value
    }
}

public class Program {
    public static void Main() {
        TreeNode root = new TreeNode(4,
            new TreeNode(2, new TreeNode(1), new TreeNode(3)),
            new TreeNode(6, new TreeNode(5), new TreeNode(7)));

        BSTIterator iterator = new BSTIterator(root);
        while (iterator.HasNext()) {
            Console.Write(iterator.Next());
            if (iterator.HasNext()) Console.Write(" -> ");
        }
        Console.WriteLine(" -> null");
    }
}

while (node != null) { stack.Push(node); // push current node to stack node = node.left; // move to left child }

push all left children to stack to reach smallest node first

TreeNode curr = stack.Pop(); // pop top node as next smallest

pop node from stack to return next smallest value

if (curr.right != null) { PushLeftPath(curr.right); // push left path of right subtree }

if popped node has right child, push its left path to stack

return curr.val; // return current node's value

return the value of the current smallest node

return stack.Count > 0; // check if any nodes left

check if iterator has more nodes to visit

Output

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> null

Complexity Analysis

Time: O(1) average per next() call because each node is pushed and popped once

Space: O(h) where h is tree height due to stack storing left path nodes

vs Alternative: Compared to recursive inorder traversal which uses call stack, this iterator uses explicit stack and allows controlled step-by-step traversal

Edge Cases

Empty tree (root is null)

Iterator stack is empty, HasNext() returns false immediately

DSA C#

while (node != null) { stack.Push(node); node = node.left; }

Tree with single node

Stack contains one node, next() returns that node's value, then empty

DSA C#

while (node != null) { stack.Push(node); node = node.left; }

Nodes with no right child

No additional nodes pushed after popping, iteration continues correctly

DSA C#

if (curr.right != null) { PushLeftPath(curr.right); }

When to Use This Pattern

When you need to traverse a BST in sorted order but want to pause and resume traversal efficiently, use a BST iterator with a stack to simulate inorder traversal step-by-step.

Common Mistakes

Mistake: Not pushing the left path of the right child after popping a node
Fix: After popping a node, always push the left path of its right child if it exists

Mistake: Pushing nodes incorrectly causing duplicates or missing nodes
Fix: Only push nodes when moving down left children, never push right child directly without left descent

Summary

It provides a way to visit BST nodes in ascending order one by one using a controlled iterator.

Use it when you want to traverse a BST lazily without recursion or building a full list.

The key insight is to use a stack to remember the path to the next smallest node by pushing left children.

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