BST Iterator Design in DSA Java - Execution Trace

Concept Flow - BST Iterator Design

Initialize stack empty

↓

Push all left nodes from root

↓

Check if stack empty?

Yes→No next element

No↓

Pop top node from stack

↓

Return popped node's value

↓

Push all left nodes from popped node's right child

↩Back to Check if stack empty?

The iterator uses a stack to store nodes. It pushes all left children from the root initially. Each next() pops the top node, returns its value, then pushes all left children of the popped node's right child.

Execution Sample

DSA Java

class BSTIterator {
  Stack<TreeNode> stack = new Stack<>();
  public BSTIterator(TreeNode root) {
    pushLeft(root);
  }
  private void pushLeft(TreeNode node) {
    while(node != null) { stack.push(node); node = node.left; }
  }
  public int next() {
    TreeNode top = stack.pop();
    pushLeft(top.right);
    return top.val;
  }
  public boolean hasNext() {
    return !stack.isEmpty();
  }
}

This code creates an iterator for BST that returns nodes in ascending order using a stack to track left nodes.

Execution Table

Step	Operation	Nodes in Stack (top->bottom)	Pointer Changes	Visual State (BST nodes with stack top marked)
1	Initialize iterator with root=7	[1,3,7]	Push 7, then 3, then 1	BST: 7 / \ 3 15 / \ \ 1 5 18 Stack top->1->3->7
2	Call next()	[3,7]	Pop 1 from stack, Return 1	BST same, stack top->3->7
3	Call next()	[5,7]	Pop 3, push left nodes of 3.right=5, Push 5, Return 3	BST same, stack top->5->7
4	Call next()	[7]	Pop 5, 5.right=null no push, Return 5	BST same, stack top->7
5	Call next()	[15]	Pop 7, push left nodes of 7.right=15, Push 15 (15.left=null no push), Return 7	BST same, stack top->15
6	Call next()	[18]	Pop 15, push left nodes of 15.right=18, Push 18, Return 15	BST same, stack top->18
7	Call next()	[]	Pop 18, 18.right=null no push, Return 18	BST same, stack empty
8	Call hasNext()	[]	No change	Return false, Stack empty

💡 Stack empty means no more nodes to visit; iteration ends.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8
stack	[]	[1,3,7]	[3,7]	[5,7]	[7]	[15]	[18]	[]	[]
current node (top of stack)	null	1	3	5	7	15	18	null	null
output (last returned)	null	null	1	3	5	7	15	18	null

Key Moments - 3 Insights

Why do we push all left children initially and after popping a node?

Because the smallest elements are on the left, pushing all left nodes ensures the next smallest is on top of the stack. See execution_table steps 1 and 3 where pushLeft is called.

What happens if the popped node has no right child?

No nodes are pushed after popping. The stack just shrinks by one. See execution_table steps 4 and 7 where no push occurs after popping 5 and 18.

How does hasNext() know if there are more nodes?

It checks if the stack is empty. If empty, no more nodes remain. See execution_table step 8 where stack is empty and hasNext returns false.

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, what is the top node in the stack after next() is called?

A Node with value 3

B Node with value 5

C Node with value 7

D Node with value 1

💡 Hint

Check the 'Nodes in Stack' column at Step 3 in execution_table

At which step does the stack become empty?

A Step 7

B Step 6

C Step 8

D Step 5

💡 Hint

Look at the 'Nodes in Stack' column and find when it shows []

If the BST had no right children at all, how would the stack change after each next() call?

A Stack size increases after each next()

B Stack size stays the same

C Stack size decreases by one each next() call

D Stack becomes empty immediately

💡 Hint

Refer to variable_tracker for stack size changes when no right child is pushed

Concept Snapshot

BST Iterator uses a stack to traverse nodes in ascending order.
Initialize by pushing all left nodes from root.
next() pops top node, returns its value, then pushes left nodes of popped node's right child.
hasNext() checks if stack is empty.
This simulates in-order traversal with O(h) space, h = tree height.

Full Transcript

The BST Iterator design uses a stack to simulate in-order traversal of a binary search tree. Initially, all left children from the root are pushed onto the stack, so the smallest element is on top. Each call to next() pops the top node, returns its value, and then pushes all left children of the popped node's right child. This ensures the next smallest element is always on top of the stack. The hasNext() method simply checks if the stack is empty to determine if more elements remain. The execution table shows step-by-step how nodes are pushed and popped, and how the stack changes. Key moments clarify why left nodes are pushed and what happens when nodes have no right child. The visual quiz tests understanding of stack state at various steps. This iterator provides an efficient way to traverse BST in sorted order using O(h) memory, where h is the tree height.

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