BST Iterator Design in DSA Python - Time & Space Complexity

Time Complexity: BST Iterator Design

O(1)

Understanding Time Complexity

We want to understand how fast the BST Iterator works when we ask for the next smallest element.

How does the time to get each next element change as the tree grows?

Scenario Under Consideration

Analyze the time complexity of the following BST Iterator code snippet.

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

This code creates an iterator that returns the next smallest value in a binary search tree each time next() is called.

Identify Repeating Operations

Look at what repeats when we call next() multiple times.

• Primary operation: Pushing left children of a node onto the stack.
• How many times: Each node is pushed and popped exactly once during the entire iteration.

How Execution Grows With Input

Each node is handled once, but the work per next() call varies.

Input Size (n)	Approx. Operations per next()
10	About 1 push/pop on average
100	About 1 push/pop on average
1000	About 1 push/pop on average

Pattern observation: Although some next() calls do more work, on average each call does a small constant amount of work.

Final Time Complexity

Time Complexity: O(1) amortized per next() call

This means each call to next() takes constant time on average, even if some calls do more work.

Common Mistake

[X] Wrong: "Each next() call always takes O(h) time because of the while loop."

[OK] Correct: The while loop work is spread out over all nodes, so each node is pushed once. This means the average time per next() is constant, not O(h).

Interview Connect

Understanding amortized time helps you explain why some operations seem slow sometimes but are fast overall. This skill shows you can analyze real-world data structures deeply.

Self-Check

What if we changed the iterator to store all nodes in a list upfront? How would the time complexity of next() change?

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