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?"