BST Iterator Design in DSA Python - Execution Trace

Concept Flow - BST Iterator Design

Initialize stack empty

↓

Push left nodes from root

↓

HasNext?

No→End

|Yes↓

Pop top node

↓

Return node value

↓

Push left nodes from popped node's right child

↩Back to HasNext?

The iterator uses a stack to store left nodes from the current subtree. On next(), it pops the top node, returns its value, then pushes left nodes from its right child.

Execution Sample

DSA Python

class BSTIterator:
    def __init__(self, root):
        self.stack = []
        self._push_left(root)

    def _push_left(self, node):
        while node:
            self.stack.append(node)
            node = node.left

    def next(self):
        top = self.stack.pop()
        self._push_left(top.right)
        return top.val

    def hasNext(self):
        return len(self.stack) > 0

This code creates an iterator over a BST that returns nodes in ascending order using a controlled stack of left nodes.

Execution Table

Step	Operation	Nodes in Stack (Top to Bottom)	Pointer Changes	Visual State (Stack Content)
1	Initialize iterator with root=7	[7, 3, 1]	Push left nodes 7->3->1	Stack: 1(top) -> 3 -> 7(bottom)
2	hasNext()	Stack unchanged	Check stack length > 0	Stack: 1 -> 3 -> 7
3	next()	Pop 1	Pop node 1; push left nodes from 1.right (None)	Stack: 3 -> 7
4	hasNext()	Stack unchanged	Check stack length > 0	Stack: 3 -> 7
5	next()	Pop 3	Pop node 3; push left nodes from 3.right (4)	Stack: 4 -> 7
6	hasNext()	Stack unchanged	Check stack length > 0	Stack: 4 -> 7
7	next()	Pop 4	Pop node 4; push left nodes from 4.right (None)	Stack: 7
8	hasNext()	Stack unchanged	Check stack length > 0	Stack: 7
9	next()	Pop 7	Pop node 7; push left nodes from 7.right (9->8)	Stack: 8 -> 9
10	hasNext()	Stack unchanged	Check stack length > 0	Stack: 8 -> 9
11	next()	Pop 8	Pop node 8; push left nodes from 8.right (None)	Stack: 9
12	hasNext()	Stack unchanged	Check stack length > 0	Stack: 9
13	next()	Pop 9	Pop node 9; push left nodes from 9.right (None)	Stack: empty
14	hasNext()	Stack empty	Check stack length == 0	Stack: empty

💡 Stack is empty, no more nodes to visit, iteration ends.

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	After Step 9	After Step 11	After Step 13	Final
stack	[7,3,1]	[7,3]	[7,4]	[7]	[9,8]	[9]	[]	[]
current_node	7	1	3	4	7	8	9	None
output_values	[]	[1]	[1,3]	[1,3,4]	[1,3,4,7]	[1,3,4,7,8]	[1,3,4,7,8,9]	[1,3,4,7,8,9]

Key Moments - 3 Insights

Why do we push all left nodes from the right child after popping a node?

After popping a node, its right subtree contains nodes greater than it. We push all left nodes from that right child to maintain ascending order. See steps 5 and 9 in execution_table where after popping 3 and 7, left nodes from their right children are pushed.

Why does hasNext() only check if the stack is not empty?

The stack always holds the next nodes to visit in ascending order. If it's empty, no nodes remain. This is shown in steps 2, 4, 6, 8, 10, 12, and 14 where hasNext() returns True until the stack empties.

What happens if the BST is empty at initialization?

If root is None, the stack remains empty after initialization, so hasNext() immediately returns False, ending iteration early. This is implied by the initial push left operation in step 1.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, which node is popped and what nodes are pushed afterward?

A Pop 3; push left nodes from 3.right (4)

B Pop 1; push left nodes from 1.right (None)

C Pop 7; push left nodes from 7.right (9,8)

D Pop 4; push left nodes from 4.right (None)

💡 Hint

Check the 'Operation' and 'Pointer Changes' columns at step 5 in execution_table.

At which step does the stack become empty, causing hasNext() to return False?

A Step 13

B Step 14

C Step 12

D Step 10

💡 Hint

Look at the 'Nodes in Stack' column and 'exit_note' in execution_table.

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

A Stack would become empty immediately after initialization

B Stack would push right children after each pop

C Stack would only pop nodes without pushing new ones

D Stack would push left children repeatedly

💡 Hint

Refer to the 'Pointer Changes' column where pushing left nodes from right child happens only if right child exists.

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 from popped node's right child.
hasNext() checks if stack is not empty.
This simulates controlled in-order traversal with O(h) space.

Full Transcript

The BST Iterator design uses a stack to simulate in-order traversal of a binary search tree. Initially, it pushes all left nodes from the root onto the stack. Each call to next() pops the top node from the stack, returns its value, and then pushes all left nodes from the popped node's right child. The hasNext() method simply checks if the stack is not empty, indicating more nodes to visit. This approach ensures nodes are returned in ascending order with efficient space usage proportional to the tree height.

Practice

1. What is the main purpose of a BST Iterator in a binary search tree?

easy

A. To balance the BST automatically

B. To insert new nodes into the BST

C. To traverse the BST in ascending order without recursion

D. To delete nodes from the BST

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.

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 C

4. Quick Check:

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

Hint: BST Iterator returns next smallest element step-by-step [OK]

Common Mistakes:

• Confusing iterator with insertion or deletion
• Thinking it balances the tree automatically
• Assuming it uses recursion internally

2. Which of the following is the correct way to initialize a stack in Python for implementing a BST Iterator?

easy

A. stack = []

B. stack = {}

C. stack = ()

D. stack = set()

Solution

1. Step 1: Identify the correct data structure for stack

   In Python, a stack is commonly implemented using a list, which supports push and pop operations.

2. Step 2: Match the syntax

   An empty list is created with [], so stack = [] is correct.

3. Final Answer:

   stack = [] -> Option A

4. Quick Check:

   Stack uses list [] in Python [OK]

Hint: Use list [] for stack, not dict or set [OK]

Common Mistakes:

• Using {} which creates a dictionary, not a stack
• Using () which creates a tuple, immutable
• Using set() which is unordered

3. What will be the output of the following code snippet using a BST Iterator?

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class BSTIterator:
    def __init__(self, root):
        self.stack = []
        self._push_left(root)
    def _push_left(self, node):
        while node:
            self.stack.append(node)
            node = node.left
    def next(self):
        node = self.stack.pop()
        self._push_left(node.right)
        return node.val

root = TreeNode(2, TreeNode(1), TreeNode(3))
iterator = BSTIterator(root)
print(iterator.next())
print(iterator.next())
print(iterator.next())

medium

A. 2
1
3

B. 1
2
3

C. 3
2
1

D. 1
3
2

Solution

1. Step 1: Understand the BST structure and iterator initialization

   The BST has root 2, left child 1, right child 3. The iterator pushes all left nodes starting from root, so stack = [2,1].

2. Step 2: Trace the next() calls

   First next(): pop 1, push left of 1's right (None), output 1.
   Second next(): pop 2, push left of 2's right (3), stack = [3], output 2.
   Third next(): pop 3, push left of 3's right (None), output 3.

3. Final Answer:

   1 2 3 -> Option B

4. Quick Check:

   In-order traversal = 1, 2, 3 [OK]

Hint: BST Iterator outputs nodes in ascending order [OK]

Common Mistakes:

• Confusing order of popping from stack
• Not pushing left children of right subtree
• Assuming preorder or postorder traversal

4. Identify the bug in this BST Iterator implementation:

class BSTIterator:
    def __init__(self, root):
        self.stack = []
        self._push_left(root)
    def _push_left(self, node):
        while node:
            self.stack.append(node)
            node = node.right  # Bug here
    def next(self):
        node = self.stack.pop()
        self._push_left(node.right)
        return node.val

medium

A. In _push_left, should traverse left child, not right child

B. Stack should be initialized as a set, not list

C. next() should return node.key instead of node.val

D. Missing base case for empty tree in __init__

Solution

1. Step 1: Analyze the _push_left method

   The method is supposed to push all left children to the stack to simulate in-order traversal, but it incorrectly moves to the right child in the loop.

2. Step 2: Identify the correct traversal direction

   It should move to the left child (node = node.left) to push left nodes, so In _push_left, should traverse left child, not right child is correct.

3. Final Answer:

   In _push_left, should traverse left child, not right child -> Option A

4. Quick Check:

   _push_left must go left, not right [OK]

Hint: Left subtree traversal uses node.left, not node.right [OK]

Common Mistakes:

• Confusing left and right child traversal
• Using set instead of list for stack
• Returning wrong attribute from node

5. You want to design a BST Iterator that supports hasNext() and next() methods. Which approach best balances time and space complexity for large BSTs?

hard

A. Store all nodes in a list during initialization and iterate over it

B. Use recursion to traverse the BST each time next() is called

C. Store only the root node and traverse the tree from root every time

D. Use a stack to push left nodes on demand during iteration

Solution

1. Step 1: Evaluate storing all nodes upfront

   Storing all nodes in a list uses O(n) space and time upfront, which is inefficient for large trees.

2. Step 2: Consider stack-based on-demand traversal

   Using a stack to push left nodes only when needed uses O(h) space (h = tree height) and provides efficient next() calls.

3. Step 3: Analyze recursion and root-only traversal

   Recursion each next() call is inefficient and root-only traversal repeats work, both are poor choices.

4. Final Answer:

   Use a stack to push left nodes on demand during iteration -> Option D

5. Quick Check:

   Stack-based lazy traversal balances time and space [OK]

Hint: Use stack for lazy traversal, not full list or recursion [OK]

Common Mistakes:

• Preloading entire tree wastes memory
• Using recursion repeatedly causes overhead
• Restarting traversal from root wastes time