BST Iterator Design in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the stack in the BST Iterator constructor.

DSA Python

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

    def _leftmost_inorder(self, node):
        while node is not None:
            self.stack.[1](node)
            node = node.left

Drag options to blanks, or click blank then click option'

Apop

Bremove

Cappend

Dinsert

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'pop' instead of 'append' which removes elements.

Using 'remove' which deletes a specific element, not adding.

Using 'insert' without specifying index.

We use 'append' to add nodes to the stack as we traverse left.

2fill in blank

medium

Complete the code to check if the iterator has a next smallest number.

DSA Python

def hasNext(self):
    return [1] > 0

Drag options to blanks, or click blank then click option'

Aself.stack.pop()

Blen(self.stack)

Cself.stack[-1]

Dself.stack

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'self.stack' directly which returns a list, not a boolean.

Using 'self.stack[-1]' which accesses the last element but does not check if stack is empty.

Using 'pop' which removes an element instead of checking.

We check if the stack length is greater than zero to know if there is a next element.

3fill in blank

hard

Fix the error in the next() method to pop the top node from the stack.

DSA Python

def next(self):
    top_node = self.stack.[1]()
    if top_node.right is not None:
        self._leftmost_inorder(top_node.right)
    return top_node.val

Drag options to blanks, or click blank then click option'

Apop

Binsert

Cremove

Dappend

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'append' which adds instead of removing.

Using 'remove' which deletes a specific element but does not return it.

Using 'insert' which adds elements at a position.

We use 'pop' to remove and return the last element from the stack.

4fill in blank

hard

Fill both blanks to complete the _leftmost_inorder helper method for the BST Iterator.

DSA Python

def _leftmost_inorder(self, node):
    while node is not None:
        self.stack.[1](node)
        node = node.[2]

Drag options to blanks, or click blank then click option'

Aappend

Bpop

Cleft

Dright

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'pop' instead of 'append' to add nodes.

Moving to the right child instead of left.

We append nodes to the stack and move to the left child to reach the smallest node.

5fill in blank

hard

Fill all three blanks to complete the next() method that returns the next smallest value in the BST.

DSA Python

def next(self):
    top_node = self.stack.[1]()
    if top_node.[2] is not None:
        self._leftmost_inorder(top_node.[3])
    return top_node.val

Drag options to blanks, or click blank then click option'

Aappend

Bpop

Cright

Dleft

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'append' instead of 'pop' to get the top node.

Checking the left child instead of right.

Passing the left child to _leftmost_inorder instead of right.

We pop the top node, check if it has a right child, and if so, traverse its leftmost nodes.

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