BST Iterator Design in DSA Go - Time & Space Complexity

Time Complexity: BST Iterator Design

O(1) amortized

Understanding Time Complexity

We want to understand how fast the BST Iterator works when moving through a tree.

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

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// BST Iterator struct
// Uses a stack to store nodes
// Pushes left children first

func (it *BSTIterator) Next() int {
    node := it.stack[len(it.stack)-1]
    it.stack = it.stack[:len(it.stack)-1]
    val := node.Val
    node = node.Right
    for node != nil {
        it.stack = append(it.stack, node)
        node = node.Left
    }
    return val
}
    

This code returns the next smallest value in a binary search tree by using a stack to track nodes.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for loop that pushes left children of the right subtree onto the stack.
• How many times: Each node is pushed and popped exactly once during the entire iteration.

How Execution Grows With Input

Each call to Next() does a small amount of work plus pushes some nodes from the right subtree.

Input Size (n)	Approx. Operations per Next()
10	About 1 to 3 node pushes/pops
100	Still about 1 to few node pushes/pops
1000	Usually 1 to few node pushes/pops

Pattern observation: Each node is handled once, so work per Next() call averages out to a small constant.

Final Time Complexity

Time Complexity: O(1) amortized

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

Common Mistake

[X] Wrong: "Each Next() call always takes O(n) time because it may push many nodes."

[OK] Correct: Over all calls, each node is pushed and popped once, so the total work spreads out, making each call fast on average.

Interview Connect

Understanding this iterator shows you can manage tree traversal efficiently without recursion, a useful skill in many coding problems.

Self-Check

"What if we changed the iterator to use recursion instead of a stack? How would the time complexity 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 explicitly.

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 in order [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 method signature for the Next() function in a BST Iterator in Go?

easy

A. func (it *BSTIterator) Next() int

B. func Next(it BSTIterator) int

C. func (it BSTIterator) Next() int

D. func Next() int

Solution

1. Step 1: Understand method receiver in Go

   Methods with pointer receivers allow modifying the iterator's internal state, which is needed for Next().

2. Step 2: Identify correct signature

   func (it *BSTIterator) Next() int uses pointer receiver *BSTIterator and returns an int, matching the expected signature.

3. Final Answer:

   func (it *BSTIterator) Next() int -> Option A

4. Quick Check:

   Pointer receiver + return int = func (it *BSTIterator) Next() int [OK]

Hint: Use pointer receiver to update iterator state [OK]

Common Mistakes:

• Using value receiver which copies state
• Defining Next as a standalone function
• Omitting receiver entirely

3. Given the BST with nodes 7, 3, 15, 9, 20 inserted in that order, what will be the output of calling Next() three times on a correctly implemented BST Iterator?

medium

A. [3, 7, 9]

B. [7, 9, 15]

C. [3, 9, 15]

D. [7, 3, 9]

Solution

1. Step 1: Build BST and find in-order traversal

   Inserting 7, 3, 15, 9, 20 creates BST with in-order: 3, 7, 9, 15, 20.

2. Step 2: Identify first three Next() outputs

   Calling Next() three times returns first three smallest elements: 3, 7, 9.

3. Final Answer:

   [3, 7, 9] -> Option A

4. Quick Check:

   In-order first 3 = [3,7,9] [OK]

Hint: Next() returns next smallest in sorted order [OK]

Common Mistakes:

• Confusing insertion order with traversal order
• Mixing up left and right child positions
• Assuming Next() returns inserted order

4. Consider this buggy Go code snippet for BST Iterator's HasNext() method:

func (it *BSTIterator) HasNext() bool {
    return len(it.stack) > 0
}

What is the main issue if the stack is not properly initialized during iterator creation?

medium

A. HasNext() incorrectly modifies the stack contents

B. HasNext() will cause a runtime panic due to nil slice access

C. HasNext() always returns true regardless of stack state

D. HasNext() may return false even if nodes remain unvisited

Solution

1. Step 1: Understand stack role in BST Iterator

   The stack holds nodes to visit; if not initialized, it may be empty even if tree has nodes.

2. Step 2: Analyze HasNext() behavior

   HasNext() checks stack length; if stack is empty due to no initialization, it returns false prematurely.

3. Final Answer:

   HasNext() may return false even if nodes remain unvisited -> Option D

4. Quick Check:

   Uninitialized stack = false HasNext() early [OK]

Hint: Initialize stack with leftmost nodes before HasNext() [OK]

Common Mistakes:

• Assuming nil slice causes panic on len()
• Expecting HasNext() to modify stack
• Ignoring stack initialization in constructor

5. You want to design a BST Iterator that supports Next() and HasNext() with O(1) average time and O(h) space, where h is tree height. Which approach best achieves this?

hard

A. Store all nodes in a slice during initialization and iterate over it

B. Use a stack to store leftmost nodes and push right child nodes lazily during Next()

C. Use recursion to traverse nodes on each Next() call

D. Use a queue to store nodes in level order and dequeue on Next()

Solution

1. Step 1: Analyze time and space constraints

   O(1) average time per Next() and O(h) space means no full traversal upfront.

2. Step 2: Evaluate approaches

   Use a stack to store leftmost nodes and push right child nodes lazily during Next() uses a stack with lazy pushing of right children, matching constraints efficiently.

3. Step 3: Reject other options

   Store all nodes in a slice during initialization and iterate over it uses O(n) space, C uses recursion (not O(1) average), D uses queue with level order, not sorted order.

4. Final Answer:

   Use a stack to store leftmost nodes and push right child nodes lazily during Next() -> Option B

5. Quick Check:

   Stack + lazy push = O(1) avg time, O(h) space [OK]

Hint: Use stack with lazy right child push for efficient iteration [OK]

Common Mistakes:

• Preloading all nodes wastes space
• Using recursion breaks O(1) average time
• Using queue breaks sorted order iteration