BST Iterator Design in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of BST Iterator next() calls

Given the BST Iterator initialized with the BST below, what is the output sequence of calling next() three times?

DSA Python

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

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

# BST structure:
#       7
#      / \
#     3   15
#         / \
#        9  20

root = TreeNode(7, TreeNode(3), TreeNode(15, TreeNode(9), TreeNode(20)))
iterator = BSTIterator(root)
output = [iterator.next(), iterator.next(), iterator.next()]

A [3, 7, 9]

B [7, 3, 9]

C [3, 9, 7]

D [7, 9, 15]

💡 Hint

Remember that BST Iterator returns elements in ascending order using in-order traversal.

The BST Iterator uses a stack to simulate in-order traversal. The first next() returns the smallest element 3, then 7, then 9.

🧠 Conceptual

intermediate

BST Iterator hasNext() behavior

After initializing a BST Iterator on a BST with nodes [5, 3, 7], which statement about hasNext() is true immediately after initialization?

A hasNext() returns False because the iterator is empty

B hasNext() returns False because no nodes have been visited yet

C hasNext() returns True because the stack is not empty

D hasNext() returns True only after calling next() once

💡 Hint

Think about what the stack contains right after initialization.

The iterator pushes all left nodes from root to the stack during initialization, so stack is not empty and hasNext() returns True.

🔧 Debug

advanced

Identify the error in BST Iterator next() method

What error will occur when calling next() on this BST Iterator implementation if the stack is empty?

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):
        node = self.stack.pop()
        self._push_left(node.right)
        return node.val

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

iterator = BSTIterator(None)
iterator.next()

A AttributeError: 'NoneType' object has no attribute 'val'

B IndexError: pop from empty list

C TypeError: 'NoneType' object is not iterable

D No error, returns None

💡 Hint

What happens if you pop from an empty list in Python?

Calling pop() on an empty list raises IndexError in Python.

🚀 Application

advanced

Number of next() calls to reach a value

Given a BST Iterator initialized on the BST below, how many calls to next() are needed to get the value 15?

DSA Python

# BST structure:
#       10
#      /  \
#     5    15
#    / \     \
#   3   7     20

root = TreeNode(10, TreeNode(5, TreeNode(3), TreeNode(7)), TreeNode(15, None, TreeNode(20)))
iterator = BSTIterator(root)
count = 0
while iterator.hasNext():
    val = iterator.next()
    count += 1
    if val == 15:
        break

A 4

B 3

C 2

D 5

💡 Hint

Remember the iterator returns nodes in ascending order.

The in-order traversal order is [3,5,7,10,15,20]. 15 is the 5th element, so 4 calls before it, 5th call returns 15.

❓ Predict Output

expert

Output after mixed next() and hasNext() calls

What is the output of the following code snippet?

DSA Python

root = TreeNode(8, TreeNode(3, TreeNode(1), TreeNode(6)), TreeNode(10, None, TreeNode(14)))
iterator = BSTIterator(root)
results = []
results.append(iterator.hasNext())  # 1
results.append(iterator.next())     # 2
results.append(iterator.next())     # 3
results.append(iterator.hasNext())  # 4
results.append(iterator.next())     # 5
results.append(iterator.hasNext())  # 6
results.append(iterator.next())     # 7
results.append(iterator.hasNext())  # 8
results.append(iterator.next())     # 9
results.append(iterator.hasNext())  # 10

A [true, 1, 3, true, 6, true, 8, true, 10, false]

B [true, 1, 3, true, 6, true, 8, true, 10, true]

C [true, 1, 3, true, 6, true, 8, false, 10, false]

D [true, 1, 3, false, 6, true, 8, true, 10, true]

💡 Hint

Trace the iterator calls carefully and remember hasNext() returns False only when no nodes remain.

The in-order traversal is [1,3,6,8,10,14]. After 4 next() calls, 10 is returned. The last hasNext() returns True before 14, but after 10, hasNext() is True. After 10 next(), hasNext() is False.

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