BST Iterator Design in DSA Java

Mental Model

A BST iterator lets you visit nodes in order without storing all nodes at once. It uses a stack to remember where to go next.

Analogy: Imagine reading a book with bookmarks. You only keep bookmarks for pages you might return to, so you don't have to remember the whole book at once.

      7
     / \
    3   15
       /  \
      9    20
Stack: []
Next node to visit: 3 (leftmost)

Dry Run Walkthrough

Input: BST with nodes 7, 3, 15, 9, 20; iterate in ascending order

Goal: Visit nodes in ascending order: 3, 7, 9, 15, 20 using the iterator

Step 1: Initialize iterator by pushing leftmost nodes onto stack

Stack: [7, 3]
Next node to visit: top of stack (3)

Why: We start at the smallest node by going left as far as possible

Step 2: Call next(), pop 3 from stack

Stack: [7]
Returned: 3
Next node to visit: 7

Why: 3 has no right child, so next is parent 7

Step 3: Call next(), pop 7 from stack and push leftmost of right subtree (15, 9)

Stack: [15, 9]
Returned: 7
Next node to visit: 9

Why: After 7, move to right subtree starting at 15, go left to 9

Step 4: Call next(), pop 9 from stack

Stack: [15]
Returned: 9
Next node to visit: 15

Why: 9 has no right child, so next is parent 15

Step 5: Call next(), pop 15 from stack and push leftmost of right subtree (20)

Stack: [20]
Returned: 15
Next node to visit: 20

Why: After 15, move to right child 20

Step 6: Call next(), pop 20 from stack

Stack: []
Returned: 20
Next node to visit: none (stack empty)

Why: 20 has no children, iteration ends

Result:

3 -> 7 -> 9 -> 15 -> 20 -> null

Annotated Code

DSA Java

import java.util.Stack;

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

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

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

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

    public boolean hasNext() {
        return !stack.isEmpty(); // check if nodes remain
    }

    public int next() {
        TreeNode curr = stack.pop(); // get next smallest
        if (curr.right != null) {
            pushLeft(curr.right); // push left path of right subtree
        }
        return curr.val; // return current node value
    }
}

public class Main {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(7);
        root.left = new TreeNode(3);
        root.right = new TreeNode(15);
        root.right.left = new TreeNode(9);
        root.right.right = new TreeNode(20);

        BSTIterator iterator = new BSTIterator(root);
        StringBuilder sb = new StringBuilder();
        while (iterator.hasNext()) {
            sb.append(iterator.next()).append(" -> ");
        }
        sb.append("null");
        System.out.println(sb.toString());
    }
}

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

push all left children to stack to reach smallest node

return !stack.isEmpty();

check if there are nodes left to visit

TreeNode curr = stack.pop();

pop next smallest node from stack

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

if right child exists, push its leftmost path

return curr.val;

return value of current node

Output

3 -> 7 -> 9 -> 15 -> 20 -> null

Complexity Analysis

Time: O(1) amortized 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 storing all nodes in a list (O(n) space), this uses less memory and supports lazy traversal

Edge Cases

Empty tree

hasNext() returns false immediately, next() is not called

DSA Java

return !stack.isEmpty();

Tree with single node

stack contains one node, next() returns that node then empty

DSA Java

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

Right skewed tree

pushLeft pushes one node at a time, next() visits nodes in order

DSA Java

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

When to Use This Pattern

When you need to traverse a BST in sorted order but want to use O(h) space and get next smallest on demand, use the BST Iterator pattern with a stack.

Common Mistakes

Mistake: Pushing all nodes into a list at once, losing lazy traversal benefit
Fix: Use a stack to push only left children and push right subtree lazily

Mistake: Not pushing left children of right subtree after popping a node
Fix: After popping, if right child exists, push its leftmost path

Summary

Provides an iterator to traverse BST nodes in ascending order using a stack.

Use when you want sorted traversal without storing all nodes upfront.

The key is to push left children to stack and handle right subtrees lazily.

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