BST Iterator Design in DSA Python

Mental Model

A BST iterator lets you see the tree's values in order, one by one, without storing them all at once.

Analogy: Imagine reading a book page by page instead of copying the whole book first; you only keep the current page and a bookmark to know where to go next.

       7
      / \
     3   15
        /  \
       9    20

Stack: [7]
Current: null

Dry Run Walkthrough

Input: BST with nodes 7, 3, 15, 9, 20; iterate to get next smallest values

Goal: To get the next smallest value each time we call next(), using O(h) space where h is tree height

Step 1: Initialize iterator by pushing left children from root

Stack: [7, 3]
Next call to next() will pop 3

Why: We start with the smallest element on top of the stack

Step 2: Call next(), pop 3 from stack

Stack: [7]
Returned value: 3

Why: 3 is the smallest node, so we return it first

Step 3: Call next(), pop 7 from stack and push left children of 7's right child (15)

Stack: [15, 9]
Returned value: 7

Why: After 7, next smallest is leftmost node in 7's right subtree

Step 4: Call next(), pop 9 from stack

Stack: [15]
Returned value: 9

Why: 9 is next smallest after 7

Step 5: Call next(), pop 15 from stack and push left children of 15's right child (20)

Stack: [20]
Returned value: 15

Why: After 15, next smallest is 20

Step 6: Call next(), pop 20 from stack

Stack: []
Returned value: 20

Why: 20 is the largest node, last to return

Result:

Stack: []
Returned values in order: 3 -> 7 -> 9 -> 15 -> 20

Annotated Code

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: TreeNode):
        self.stack = []
        self._push_left(root)

    def _push_left(self, node: TreeNode):
        while node:
            self.stack.append(node)  # push node to stack
            node = node.left         # move to left child

    def next(self) -> int:
        node = self.stack.pop()      # pop top node (next smallest)
        val = node.val
        if node.right:
            self._push_left(node.right)  # push left children of right subtree
        return val

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

# Driver code to test
root = TreeNode(7)
root.left = TreeNode(3)
root.right = TreeNode(15, TreeNode(9), TreeNode(20))

iterator = BSTIterator(root)
result = []
while iterator.hasNext():
    result.append(iterator.next())
print(' -> '.join(map(str, result)) + ' -> null')

self._push_left(root)

initialize stack with leftmost path from root

while node: self.stack.append(node) node = node.left

push all left children to stack to reach smallest node

node = self.stack.pop()

pop next smallest node from stack

if node.right: self._push_left(node.right)

if right child exists, push its leftmost path to stack

return val

return the value of the current smallest node

return len(self.stack) > 0

check if there are more nodes to visit

Output

3 -> 7 -> 9 -> 15 -> 20 -> null

Complexity Analysis

Time: O(1) amortized per next() call because each node is pushed and popped once

Space: O(h) where h is the height of the tree, due to stack storing left path

vs Alternative: Compared to inorder traversal storing all nodes (O(n) space), this uses less memory by storing only the path to next node

Edge Cases

Empty tree (root is None)

Iterator stack is empty; hasNext() returns False immediately

DSA Python

self._push_left(root) handles None by not pushing anything

Tree with single node

Stack has one node; next() returns that node and then hasNext() is False

DSA Python

while node: loop pushes single node correctly

Tree with only left children

Stack initially contains all nodes; next() pops them in order

DSA Python

self._push_left pushes all left nodes on initialization

When to Use This Pattern

When you need to iterate over a BST in sorted order without using extra space for all nodes, use the BST Iterator pattern with a controlled stack.

Common Mistakes

Mistake: Pushing all nodes of the tree onto the stack at once, losing the space advantage
Fix: Only push left children of the current node to keep stack size minimal

Mistake: Not pushing left children of the right subtree after popping a node
Fix: After popping a node, if it has a right child, push all its left descendants

Summary

Provides a way to get the next smallest element in a BST one at a time using a stack.

Use when you want to traverse a BST in order without storing all nodes at once.

The key is to keep a stack of left children to know the next smallest node efficiently.

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