BST Iterator Design in DSA Typescript - Time & Space Complexity

Time Complexity: BST Iterator Design

O(1) average per next(), O(h) worst case

Understanding Time Complexity

We want to understand how fast the BST Iterator works when we move through a binary search tree.

Specifically, how the time to get the next smallest number changes as the tree grows.

Scenario Under Consideration

Analyze the time complexity of this BST Iterator code snippet.

class BSTIterator {
  private stack: TreeNode[] = [];

  constructor(root: TreeNode | null) {
    this.pushLeft(root);
  }

  private pushLeft(node: TreeNode | null) {
    while (node) {
      this.stack.push(node);
      node = node.left;
    }
  }

  next(): number {
    const node = this.stack.pop()!;
    this.pushLeft(node.right);
    return node.val;
  }

  hasNext(): boolean {
    return this.stack.length > 0;
  }
}
    

This code creates an iterator that returns the next smallest value in a BST by using a stack to track nodes.

Identify Repeating Operations

Look at what repeats when we call next():

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

How Execution Grows With Input

Imagine the tree has n nodes.

Input Size (n)	Approx. Operations
10	About 10 pushes and 10 pops total over all next() calls.
100	About 100 pushes and 100 pops total over all next() calls.
1000	About 1000 pushes and 1000 pops total over all next() calls.

Pattern observation: The total work grows linearly with the number of nodes, but each next() call does a small part of this work.

Final Time Complexity

Time Complexity: O(1) average per next() call, O(h) worst case, where h is tree height.

This means each call to next() usually takes constant time, but sometimes it takes longer depending on the tree shape.

Common Mistake

[X] Wrong: "Each next() call always takes O(h) time because it pushes nodes."

[OK] Correct: Actually, the total pushes and pops over all calls add up to O(n), so on average each call is O(1). The expensive steps are spread out.

Interview Connect

Understanding this iterator's time complexity shows you can analyze how work spreads over many operations, a key skill for real coding problems.

Self-Check

What if we changed the iterator to use recursion instead of a stack? How would the time complexity change?