BST Iterator Design in DSA Javascript - Time & Space Complexity

Time Complexity: BST Iterator Design

O(1) amortized per next()

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 BST Iterator methods.

class BSTIterator {
  constructor(root) {
    this.stack = [];
    this._pushLeft(root);
  }

  _pushLeft(node) {
    while (node) {
      this.stack.push(node);
      node = node.left;
    }
  }

  next() {
    const node = this.stack.pop();
    if (node.right) this._pushLeft(node.right);
    return node.val;
  }

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

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

Identify Repeating Operations

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

• Primary operation: Pushing nodes onto the stack while going left down the tree.
• How many times: Each node is pushed and popped exactly once during the whole iteration.

How Execution Grows With Input

Each node is visited once, but some next() calls do more work pushing nodes.

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

Pattern observation: Total work grows linearly with number of nodes, but each next() call may vary in cost.

Final Time Complexity

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

This means on average, each call to next() takes constant time, 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 pushes happen only once per node overall, so the cost spreads out, making average next() calls fast.

Interview Connect

Understanding this iterator's time complexity shows you can analyze average costs, a key skill for real coding problems.

Self-Check

"What if the BST was replaced with a linked list? How would the time complexity of next() change?"