BST Iterator Design in DSA Python - Build from Scratch

BST Iterator Design

📖 Scenario: You are building a tool to browse through numbers stored in a special tree called a Binary Search Tree (BST). This tool will help you see the numbers in order, one by one, just like flipping through pages in a book.

🎯 Goal: Create a BST Iterator that lets you move through the tree's numbers in ascending order. You will build the tree, set up the iterator, move through the numbers step-by-step, and finally print the numbers you visited.

📋 What You'll Learn

Create a BST with the exact nodes: 7, 3, 15, 9, 20

Create a class called BSTIterator with methods __init__, next, and hasNext

Use a stack inside the iterator to track nodes

Implement next to return the next smallest number

Implement hasNext to check if more numbers remain

Print the sequence of numbers returned by the iterator's next calls

💡 Why This Matters

🌍 Real World

BST Iterators are used in databases and search engines to efficiently browse sorted data without loading everything at once.

💼 Career

Understanding BST Iterators helps in roles involving data structure optimization, coding interviews, and building efficient search or navigation features.

1

Create the BST nodes

Create a class called TreeNode with an __init__ method that takes val, left, and right. Then create the BST nodes with these exact values and connections: root node with value 7, left child 3, right child 15, and 15 has left child 9 and right child 20.

DSA Python

# Define TreeNode class and create BST nodes as described
# Your code here

Hint

Think of each node as a box holding a number and links to left and right boxes.

2

Set up the BSTIterator class

Create a class called BSTIterator with an __init__ method that takes the root node. Inside __init__, create a list called stack and call a helper method _leftmost_inorder passing the root. Define the helper method _leftmost_inorder that pushes all left children of a node onto the stack.

DSA Python

# Define BSTIterator class with __init__ and _leftmost_inorder methods
# Your code here

Hint

Use a stack to remember nodes as you go left down the tree.

3

Implement next() and hasNext() methods

Inside BSTIterator, add a method next that pops the top node from stack, saves its value, and if the popped node has a right child, calls _leftmost_inorder on that right child. Return the saved value. Also add a method hasNext that returns True if stack is not empty, otherwise False.

DSA Python

# Add next() and hasNext() methods inside BSTIterator
# Your code here

Hint

Pop from stack to get next smallest, then add right child's left path if exists.

4

Use the iterator and print the output

Create an instance of BSTIterator called iterator using the root. Use a while loop that runs while iterator.hasNext() is True. Inside the loop, call iterator.next() and print the returned values separated by spaces on one line.

DSA Python

# Create BSTIterator instance and print all values using next()
# Your code here

Hint

Use a loop to get all numbers in order and print them separated by spaces.

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